Graph Coloring

Vertex Coloring

(Discussion is about undirected graphs without self-loops)

Coloring the vertices of an undirected graph such that adjacent vertices have different colors. If G is \(k\)-colorable but not \((k-1)\)-colorable, then k is called the chromatic number of G, denoted as \(\chi(G)\).

For any graph G, \(\chi(G) \leq \Delta(G) + 1\), where \(\Delta(G)\) is the maximum degree.

Brooks' Theorem

Let G be a connected graph that is neither a complete graph nor an odd cycle. Then \(\chi(G) \leq \Delta(G)\).

Proof

Proof

Let \(|V(G)|=n\), and consider mathematical induction.

First, the statement holds trivially for \(n\leq 3\).

Next, assume the statement holds for \(n-1\). We will now gradually strengthen the proposition.

We may consider only \(\Delta(G)\)-regular graphs, because a non-regular graph can be seen as formed by deleting edges from a regular graph, and this process does not affect the conclusion.

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

Let \(\Delta:=\Delta(G)\), and suppose H is colored with \(\Delta\) colors \(c_1,c_2,\dots,c_{\Delta}\). Let the \(\Delta\) neighbors of v be \(v_1,v_1,\dots,v_{\Delta}\). Without loss of generality, assume these neighbors of v have pairwise distinct colors; otherwise, the proposition is proven.

Now, consider the subgraph \(H_{i,j}\) formed by all vertices in H colored \(c_i\) or \(c_j\) and all edges between them. Assume that any two distinct vertices \(v_i\), \(v_j\) must lie in the same connected component of \(H_{i,j}\). Otherwise, if they are in different components, we can swap the colors of all vertices in one component, making \(v_i\) and \(v_j\) have the same color.

Swapping colors here means: if the graph uses only two colors a and b, then recolor all vertices originally colored a to b, and all vertices originally colored b to a.

Let this connected component be \(C_{i,j}\). Then \(C_{i,j}\) must be a path from \(v_i\) to \(v_j\). Since the degree of \(v_i\) in H is \(\Delta-1\), the neighbors of \(v_i\) in H must have pairwise distinct colors. Otherwise, \(v_i\) could be recolored to a different color, causing a color conflict with v's other neighbors. Thus, \(v_i\) has exactly one neighbor in \(C_{i,j}\), and similarly for \(v_j\). Take a path P from \(v_i\) to \(v_j\) in \(C_{i,j}\). If \(C_{i,j}\ne P\), then traverse P and color the vertices sequentially. Let u be the first vertex encountered with degree greater than 2. Note that u's neighbors use at most \(\Delta-2\) colors, so u can be recolored to disconnect \(v_i\) and \(v_j\).

Then we can observe that for any three distinct vertices \(v_i\), \(v_j\), \(v_k\), \(V(C_{i,j})\cap V(C_{j,k})=\{v_j\}\).

At this point, the strengthening of the proposition is complete.

The remainder is straightforward. First, if all neighbors of v are pairwise adjacent, the proposition is proven. Assume \(v_1\) and \(v_2\) are not adjacent. Take w, a neighbor of \(v_1\) in \(C_{1,2}\), and swap colors in \(C_{1,3}\). In the new graph, \(w\in V(C_{1,2})\cap V(C_{2,3})\), a contradiction.

Thus, the proposition is proven.

Welsh–Powell Algorithm

The Welsh–Powell algorithm is a greedy algorithm for finding a coloring scheme without restricting the maximum number of colors.

For an 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\)

The number of colors after coloring with the Welsh–Powell algorithm is at most \(\max_{i=1}^n\min\{\deg(v_i)+1,i\}\). The time complexity of this algorithm is \(O\left(n\max_{i=1}^n\min\{\deg(v_i)+1,i\}\right)=O(n^2)\).

Process

1. Sort the currently uncolored vertices in descending order of degree.
2. Color the first vertex with an unused color.
3. Traverse the remaining vertices sequentially. If the current vertex is not adjacent to any vertex colored with the same color as the first vertex, color it with that same color.
4. If there are still uncolored vertices, return to step 1; otherwise, end.

Example:

(Generated by Graph Editor)

First, sort vertices by degree in descending order:

Order	1	2	3	4	5	6	7	8	9	10	11	12	13
Vertex ID	4	5	0	2	9	1	3	6	10	12	7	8	11
Degree	5	5	4	4	4	3	3	3	3	3	2	2	1
\(\min\{\deg(v_i)+1,i\}\)	1	2	3	4	5	4	4	4	4	4	3	3	2

Thus, the Welsh–Powell algorithm uses at most 5 colors.

Additionally, since the graph contains a subgraph \(C_3\), the chromatic number must be at least 3.

• First coloring:

  

  Color vertices 4 9 3 11. - Second coloring:

  

  Color vertices 5 2 6 7 8. - Third coloring:

  

  Color vertices 0 1 10 12.

Proof

Proof

For an 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\)

Let \(V_0=\varnothing\). We take a subset \(V_m\) from \(V(G)\setminus\bigcup_{i=0}^{m-1} V_i\), where the 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

   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, if vertices in \(V_i\) are colored with the i-th color, this coloring scheme is exactly the one given by the Welsh–Powell algorithm. Obviously,

• \(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 left inequality is obvious. Consider the right side.

First, we can deduce:

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\), so \(\deg(v)\geq m\).

Thus,

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

On the other hand, based on the construction of the sequence \(\{V_i\}\), we can observe

\(v_j\in\bigcup_{i=1}^j V_i\)

Combining the two gives the proof.

Edge Coloring

Coloring the edges of an undirected graph such that adjacent edges have different colors. If G is k-edge-colorable but not \((k-1)\)-edge-colorable, then k is called the edge chromatic number of G, denoted as \(\chi'(G)\).

Vizing's Theorem

Let G be a simple graph. Then \(\Delta(G) \leq \chi'(G) \leq \Delta(G) + 1\)

If G is bipartite, then \(\chi'(G)=\Delta(G)\)

When \(n\) is odd (\(n \neq 1\)), \(\chi'(K_n)=n\); when \(n\) is even, \(\chi'(K_n)=n-1\)

Constructive Proof of Vizing's Theorem for Bipartite Graphs

Proof

Add edges to the bipartite graph sequentially.

When trying to add edge \((x,y)\), we attempt to find the smallest unused color for \(x\) and \(y\), denoted \(l_x\) and \(l_y\) respectively.

If \(l_x=l_y\), we can directly set the edge color to \(l_x\).

Otherwise, assume \(l_x<l_y\). We try to modify the color of the edge incident to \(y\) that is colored \(l_x\) to \(l_y\).

The modification process can be approximated as a finite unique augmenting path starting from \(y\), traversing edges colored \(l_x,l_y,\cdots\) in sequence.

Since the augmenting path is finite, we can invert the colors of all edges on the path: change \(l_x\) to \(l_y\) and \(l_y\) to \(l_x\).

By properties of bipartite graphs, node \(x\) cannot be on the augmenting path; otherwise, it contradicts the minimality of \(l_x\).

Therefore, after augmentation, we can directly set the color of edge \((x,y)\) to \(l_x\).

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

Example Code UVa10615 Rooks

#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;
}

A Non-trivial Example uoj 444 Bipartite Graph

This problem was created by the author for the 2018集训队第一轮作业题.

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

The construction for the lower bound involves splitting vertices in the bipartite graph.

If \(degree \bmod k \neq 0\), split it 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 in the original graph, meaning an edge endpoint can connect to any split vertex as long as degree constraints are satisfied.

By Vizing's theorem, we can clearly construct a k-edge-coloring for this graph.

The edge deletion part is not elaborated here as it is not closely related to Vizing's theorem.

Interested readers can refer to the author's original solution.

Chromatic Polynomial

\(P(G,k)\) denotes the total number of distinct k-colorings of G.

\(P(K_n, k) = k(k-1)\cdots(k-n+1)\)

\(P(N_n, k) = k^n\)

In an undirected acyclic graph G,

1. If \(e=(v_i, v_j) \notin E(G)\), then \(P(G, k) = P(G \cup e, k)+P(G\setminus e, k)\)
2. If \(e=(v_i, v_j) \in E(G)\), then \(P(G,k)=P(G-e,k)-P(G\setminus e,k)\)

Theorem: Let \(V_1\) be a vertex cut of G, and \(G[V_1]\) be a complete subgraph of G of order \(|V_1|\). Suppose \(G-V_1\) has \(p(p \geq 2)\) connected components. Then:

\(P(G,k)=\frac{\Pi_{i=1}^{p}{(P(H_i, k))}}{P(G[V_1], k)^{p-1}}\)

where \(H_i=G[V_1 \cup V(G_i)]\)

References

1. Graph coloring - Wikipedia
2. Welsh, D. J. A.; Powell, M. B. (1967), "An upper bound for the chromatic number of a graph and its application to timetabling problems", The Computer Journal, 10 (1): 85–86

---

本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用