Graph Coloring

Let $|V(G)|=n$, and use mathematical induction.

For $n\leq 3$, the claim is obvious.

Now assume that the claim holds for $n-1$; we will strengthen the claim step by step.

We may restrict attention to $\Delta(G)$-regular graphs, because a nonregular graph can be viewed as a regular graph with some edges deleted, and this process does not affect the conclusion.

For any regular graph G that is neither complete nor an odd cycle, choose a vertex v and consider the subgraph $H:=G-v$. By the induction hypothesis, $\chi(H)\leq\Delta(H)=\Delta(G)$; it remains only to prove that inserting v into H does not affect the conclusion.

Let $\Delta:=\Delta(G)$. Suppose H is colored with $\Delta$ colors $c_1,c_2,\dots,c_{\Delta}$, and let the $\Delta$ neighbors of v be $v_1,v_1,\dots,v_{\Delta}$. We may assume that these neighbors of v have pairwise distinct colors; otherwise the claim is proved.

Now let the vertices of H colored $c_i$ or $c_j$, together with all edges between them, form the subgraph $H_{i,j}$. We may assume that any two distinct vertices $v_i$ and $v_j$ lie in the same connected component of $H_{i,j}$; otherwise, if they lay in different components, we could swap the colors of every vertex in one component, making $v_i$ and $v_j$ have the same color.

Here, swapping colors means that if a graph uses only two colors a and b, every vertex originally colored a is recolored b, and every vertex originally colored b is recolored a.

Let the component above be $C_{i,j}$. Then $C_{i,j}$ can only be a path from $v_i$ to $v_j$. Since $v_i$ has degree $\Delta-1$ in H, the colors of the neighbors of $v_i$ in H must all be distinct; otherwise we could give $v_i$ another color, causing a duplicate with the colors of v's other neighbors. Therefore, $v_i$ has exactly one neighbor in $C_{i,j}$, and $v_j$ is analogous. We then take a path in $C_{i,j}$ from $v_i$ to $v_j$ and call it P. If $C_{i,j}\ne P$, we can recolor the vertices along P in order. Let u be the first vertex encountered whose degree is greater than 2. Its neighbors use at most $\Delta-2$ colors, so u can be recolored, making $v_i$ and $v_j$ disconnected.

It is then easy to see that for any three distinct vertices $v_i$, $v_j$, and $v_k$, $V(C_{i,j})\cap V(C_{j,k})=\{v_j\}$.

The strengthening of the claim is now complete.

The rest is simple. If the neighbors of v are pairwise adjacent, the claim is proved. Otherwise, suppose $v_1$ and $v_2$ are not adjacent. In $C_{1,2}$, take the neighbor $v_1$ of w and swap the colors in $C_{1,3}$. In the resulting graph, $w\in V(C_{1,2})\cap V(C_{2,3})$, a contradiction.

This proves the claim.

For a simple undirected graph G without self-loops, let $V(G):=\{v_1,v_2,\dots,v_n\}$ satisfy

$\deg(v_i)\geq\deg(v_{i+1}),~\forall 1\leq i\leq n-1$

Set $V_0=\varnothing$. From $V(G)\setminus\bigcup_{i=0}^{m-1} V_i$, choose a subset $V_m$ whose elements satisfy

1. $v_{k_m}\in V_m$, where $k_m=\min\{k:v_k\notin\bigcup_{i=0}^{m-1} V_i\}$.

2. If

   $\{v_{i_{m,1}},v_{i_{m,2}},\dots,v_{i_{m,l_m}}\}\subset V_m,~i_{m,1}<i_{m,2}<\dots<i_{m,l_m}$

   then $v_j\in V_m$ if and only if both

   1. $j>i_{m,l_m}$;
   2. $v_j$ is not adjacent to any of $v_{i_{m,1}},v_{i_{m,2}},\dots,v_{i_{m,l_m}}$.

Clearly, coloring the vertices in $V_i$ with color i gives exactly the coloring produced by the Welsh–Powell algorithm. Clearly,

• $V_1\neq\varnothing$;
• $V_i\cap V_j=\varnothing\iff i\neq j$;
• $\exists \alpha(G)\in\Bbb{N}^*,\forall i>\alpha(G),~s.t.~ V_i=\varnothing$.

We only need to prove

$\bigcup_{i=1}^{\alpha(G)} V_i=V(G)$

where

$\chi(G)\leq\alpha(G)\leq\max_{i=1}^n\min\{\deg(v_i)+1,i\}$.

The inequality on the left is obvious; consider the right-hand inequality.

First, we readily obtain the following:

If $v\notin\bigcup_{i=1}^mV_i$, then v is adjacent to at least one vertex in each of $V_1,V_2,\dots,V_m$, and therefore $\deg(v)\geq m$.

Consequently,

$v_j\in\bigcup_{i=1}^{\deg(v_j)+1}V_i$.

On the other hand, from the construction of the sequence $\{V_i\}$, we readily see that

$v_j\in\bigcup_{i=1}^j V_i$.

Combining the two relations proves the result.

Add edges to the bipartite graph in order.

When trying to add the edge $(x,y)$, look for the smallest-numbered unused color at $x$ and $y$, and suppose these colors are $l_x$ and $l_y$, respectively.

If $l_x=l_y$, we can directly assign $l_x$ to this edge.

Otherwise, suppose $l_x<l_y$. We can try to change the color of the edge incident to vertex $y$ whose color is $l_x$ to $l_y$.

This process can be viewed approximately as a finite unique augmenting path starting at $y$ and successively traversing edges with colors $l_x,l_y,\cdots$.

Since the augmenting path is finite, we can swap the colors of all its edges: edges originally colored $l_x$ are changed to $l_y$, and edges originally colored $l_y$ are changed to $l_x$.

By the bipartite-graph property, vertex $x$ cannot be a vertex on the augmenting path; otherwise the smallest unused color would be $l_x$, a contradiction.

Thus, after the augmentation, we can assign the color of the edge connecting $x$ and $y$ to $l_x$.

The total construction time complexity is $O(nm)$.

#include <iostream>

constexpr int MAXN = 100;

int t;
int n;
char a[MAXN + 10][MAXN + 10];
int c[MAXN + 10][MAXN + 10];
int ans;

namespace graph {
struct Vertex {
  int head;
  int deg;
  int vis[MAXN + 10];
} vertex[2 * MAXN + 10], e;

struct Edge {
  int head;
  int next;
  int col;
} edge[2 * MAXN * MAXN + 10];

int ecnt;

void init() {
  for (int i = 0; i < MAXN + 10; i++) std::fill(c[i], c[i] + MAXN + 10, 0);
  for (int i = 1; i <= 2 * MAXN; i++) vertex[i] = e;
  for (int i = 0; i <= 2 * MAXN * MAXN; i++) edge[i].col = 0;
  ecnt = 1;
  ans = 0;
  return;
}

void addEdge(int tail, int head) {
  ecnt++;
  edge[ecnt].head = head;
  edge[ecnt].next = vertex[tail].head;
  vertex[tail].head = ecnt;
  vertex[tail].deg++;
  return;
}

int get(int u) {
  for (int i = 1; i <= n; i++)
    if (!vertex[u].vis[i]) return i;
  exit(1);
}

void DFS(int u, int ori, int upd) {
  if (vertex[u].vis[ori] == 0) {
    vertex[u].vis[upd] = 0;
    return;
  }
  int e = vertex[u].vis[ori];
  int v = edge[e].head;
  DFS(v, upd, ori);
  edge[e].col = upd;
  edge[e ^ 1].col = upd;
  vertex[u].vis[upd] = e;
  vertex[v].vis[upd] = e ^ 1;
  return;
}

void AddEdge(int u, int v) {
  addEdge(u, v);
  addEdge(v, u);
  return;
}

void solve() {
  for (int u = 1; u <= n; u++) {
    for (int e = vertex[u].head; e; e = edge[e].next) {
      int v = edge[e].head;
      if (edge[e].col) continue;
      int lu = get(u);
      int lv = get(v);
      if (lu < lv) DFS(v, lu, lv);
      if (lu > lv) DFS(u, lv, lu);
      int l = std::min(lu, lv);
      vertex[u].vis[l] = e;
      vertex[v].vis[l] = e ^ 1;
      edge[e].col = l;
      edge[e ^ 1].col = l;
    }
  }
}

void generate() {
  for (int u = 1; u <= n; u++) {
    for (int e = vertex[u].head; e; e = edge[e].next) {
      int v = edge[e].head;
      c[u][v - n] = edge[e].col;
    }
  }
  return;
}
}  // namespace graph

void mian() {
  graph::init();
  std::cin >> n;
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) std::cin >> a[i][j];
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      if (a[i][j] == '*') graph::AddEdge(i, j + n);
  for (int i = 1; i <= n * 2; i++) ans = std::max(ans, graph::vertex[i].deg);
  graph::solve();
  graph::generate();
  std::cout << ans << '\n';
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) std::cout << c[i][j] << ' ';
    std::cout << '\n';
  }
  return;
}

int main() {
  std::cin >> t;
  while (t--) mian();
  return 0;
}

The author created this problem as an assignment for the first round of the training team in 2018.

First, we can observe that the lower bound on the answer is the number of vertices whose degree is not a multiple of k.

The lower-bound construction splits vertices in the bipartite graph.

If $degree \bmod k \neq 0$, split the vertex into $degree/k$ vertices of degree k and one vertex of degree $degree \bmod k$.

If $degree \bmod k = 0$, split it into $degree/k$ vertices of degree k.

The split vertices have the same meaning as the original vertex, so under the degree constraint, an edge endpoint may be connected to any one of the split vertices.

By Vizing's theorem, we can clearly construct a k-coloring of the resulting graph.

The edge-deletion part is not closely related to Vizing's theorem, so it is omitted here.

Interested readers may read the solution written by the author at the time.