Graph coloring

Result 1. Proof. In K_n every two vertices are adjacent, so a proper coloring gives all n of them different colors and \chi(K_n) \ge n. One color each is proper, so \chi(K_n) \le n. \square

Result 2. Proof. Take a proper coloring of G with \chi(G) colors and keep only its values on the vertices of H. Every edge of H is an edge of G, so its ends still differ, and H is \chi(G)-colorable. A clique of size \omega(G), with the edges among its vertices, is a subgraph equal to K_{\omega(G)}, so by Result 1, \omega(G) = \chi(K_{\omega(G)}) \le \chi(G). \square

Result 3. Proof. C_n has an edge, so \chi(C_n) \ge 2. Let n be even and give i the color 1 when i is even and 2 when i is odd. The edge \{i, i + 1\} joins integers of opposite parity, and so does the closing edge \{n - 1, 0\}, since n - 1 is odd. So \chi(C_n) = 2.

Let n be odd and suppose \varphi is a proper coloring with colors 1 and 2. Along the path 0, 1, \ldots, n - 1 the colors must alternate, so \varphi(i) = \varphi(0) exactly when i is even. Then n - 1, which is even, has \varphi(n - 1) = \varphi(0), yet n - 1 and 0 are adjacent: a contradiction, so \chi(C_n) \ge 3. Alternating 1 and 2 on 0, \ldots, n - 2 and giving n - 1 the color 3 is proper, so \chi(C_n) = 3. A graph with an odd cycle has a subgraph equal to some C_n with n odd, and Result 2 gives the last claim. \square

Result 4. Proof. By induction on the number of vertices n \ge 2 (How induction works: base case, hypothesis and step). A tree on two vertices is one edge, and needs and has two colors. Let T be a tree on n + 1 \ge 3 vertices, and assume the claim for trees on n vertices. T has a leaf \ell (Trees, Result 1), and T - \ell is a tree on n \ge 2 vertices (Result 2 there), so it has a proper coloring with colors 1 and 2. The leaf has one neighbor; give \ell the other color. The result is proper, and T has an edge, so \chi(T) = 2. \square

Result 5. Proof. Each edge v_i v_j with i < j is checked when v_j is colored, and v_j avoids the colors of its earlier neighbors, so the coloring is proper. When v_i is colored it has at most \deg(v_i) \le \Delta(G) earlier neighbors, which hold at most \Delta(G) of the colors 1, 2, \ldots, \Delta(G) + 1. So one of those is free and the smallest free color is at most \Delta(G) + 1. Result 2 gives the left inequality. \square

Result 6. Proof. By induction on v, the number of vertices. A graph with one vertex needs one color. Let G be simple and planar with v \ge 2, and assume every simple planar graph with v - 1 vertices is 6-colorable. G has a vertex u of degree at most 5 (Planar graphs and Euler's formula, Result 6). G - u is a subgraph of G, so it is simple and planar, and it has v - 1 vertices; color it properly with six colors. The at most five neighbors of u use at most five of the six colors, and u takes one they do not use. \square

Result 7. Sketch, not a full proof. Run the same induction with five colors. The only trouble is a vertex u of degree 5 whose neighbors w_1, \ldots, w_5, in order around u in a plane drawing, carry all five colors 1, \ldots, 5. Look at the vertices colored 1 or 3 and the edges among them, and let K be the component of that subgraph containing w_1. Swapping colors 1 and 3 throughout K keeps the coloring proper: an edge inside K still joins 1 and 3, and an edge from K to a vertex outside it goes to a color other than 1 and 3, since otherwise that vertex would be in K. If w_3 is not in K, after the swap w_1 and w_3 both have color 3, and color 1 is free for u.

If w_3 is in K, a path from w_1 to w_3 colored only 1 and 3, together with u, is a cycle. In the plane it separates w_2 from w_4, one inside and one outside (this step rests on the Jordan curve theorem, the topology behind planarity). A path from w_2 to w_4 colored only 2 and 4 would have to meet that cycle at a vertex, but the cycle’s vertices other than u are colored 1 and 3. So w_2 and w_4 lie in different components of the subgraph colored 2 or 4, and swapping 2 and 4 in the component of w_2 frees color 2 for u.

The swapping chains are called Kempe chains. Alfred Kempe used them in 1879 in a claimed proof of four colors; in 1890 Percy Heawood found its gap and saved five colors from the argument.

Result 10. Proof. Let k = \chi(G) and let S_1, \ldots, S_k be the color classes of a proper coloring of G. Each S_i is independent in G, so every two of its vertices are adjacent in \overline{G}: S_i is a clique of \overline{G}. By Result 2, \lvert S_i \rvert \le \omega(\overline{G}) \le \chi(\overline{G}). The classes divide up all n vertices, so

1. \omega = 3, \chi = 3, \Delta + 1 = 4. The triangle 1, 2, 3 gives \chi \ge 3; color 1, 2, 3 with 1, 2, 3, then 4 with 1, and 5, 6 with 2, 3. Only 3 and 4 have degree 3, so there is no clique of size 4.
2. \chi = 2, then \chi = 3. With \{0, 3\}, the parity coloring of Result 3 still works, since 0 is even and 3 odd. With \{0, 2\}, the triangle 0, 1, 2 forces 3, and the colors 1, 2, 3, 1, 2, 3 around the cycle are proper.
3. Three slots: \{V, X\}, \{W, Y\}, \{Z\}. The graph is the cycle V, W, X, Y, Z, V, of odd length 5, so Result 3 gives \chi = 3.
4. Three periods: \{A, D\}, \{B, E\}, \{C, F\}. The edges are AB, AC, BC, CD, CE, DE, AE, BF, DF; the triangle A, B, C forces three, and each period is independent.
5. 3 colors, then 2. First order: 0 \to 1, 3 \to 1, 1 \to 2, 4 \to 2, 2 \to 3 (its neighbors 1, 3 hold 2, 1), 5 \to 3. Second order: 1, 2, 1, 2, 1, 2.
6. 4 on 8 vertices, 3 on 9. For 8: three gaps add up to 8, so some gap is at most 2, an independent set has at most 2 vertices, and 2k \ge 8 gives k \ge 4; the colors 1, 2, 3, 4, 1, 2, 3, 4 repeat only four steps apart. For 9: a triangle forces 3, and the colors 1, 2, 3 repeated three times repeat only three or six steps apart.
7. 2, then 4. Color the square in row i, column j by the parity of i + j; side neighbors differ by 1 in one coordinate. With corners, the four squares of any 2 \times 2 block touch pairwise, a clique of size 4; coloring by the parities of i and j works, since squares sharing both parities differ by 2 in a row or column and do not touch.
8. \chi = 3. Each face is a triangle, so \chi \ge 3. The only non-adjacent pairs are the three opposite pairs; use them as the three color classes.
9. \chi(C_6) = 2 and \chi(\overline{C_6}) = 3, with product 6 = n, so Result 10 holds with equality. In \overline{C_6}, 0, 2, 4 form a triangle, and \{0, 1\}, \{2, 3\}, \{4, 5\} are independent there, so they serve as color classes.
10. Induct on v \le 11. One vertex needs one color. For 2 \le v \le 11, take u of degree at most 4; G - u is simple, planar, with v - 1 \le 11 vertices, so it is 5-colorable, and the at most four neighbors of u leave a color free.
11. If some u, v are not adjacent, give both color 1 and the other n - 2 vertices the colors 2, \ldots, n - 1: proper with n - 1 colors. So \chi(G) = n forces every pair adjacent.
12. Take a proper coloring with classes S_1, \ldots, S_k. For i \ne j some edge joins S_i to S_j, or S_i \cup S_j would be independent and one color could replace two, giving k - 1. Different pairs \{i, j\} give different edges, so there are at least \binom{k}{2} edges.
13. Take a proper coloring with classes S_1, \ldots, S_k, k = \chi(G), and list S_1, then S_2, and so on. By induction along the list, greedy gives each vertex of S_i a color at most i: its earlier neighbors lie in S_1, \ldots, S_{i-1} (none in S_i, which is independent), so they hold colors at most i - 1 and some color at most i is free. So greedy uses at most k colors, and never fewer than \chi(G) = k.
14. Each component is a subgraph, so Result 2 gives \chi(G) \ge each. Color each component properly with colors 1 up to its own chromatic number; no edge joins two components, so the whole is proper and uses the largest of these numbers.
15. Let a = \chi(G) and b = \chi(\overline{G}). Since (a - b)^2 \ge 0, (a + b)^2 \ge 4ab \ge 4n by Result 10, and \displaystyle a + b \ge 2\sqrt{n}.
16. Take a proper coloring with classes S_1, \ldots, S_k. If every vertex of S_i lacked a neighbor of some color j \ne i, recolor each to such a missing color. Two recolored vertices are not adjacent, since S_i is independent, so the coloring stays proper and uses only k - 1 colors. So each S_i has a vertex with neighbors of all k - 1 other colors, of degree at least k - 1, and these k vertices lie in different classes.
17. The last step. u may have degree exactly 5 with its five neighbors carrying all five colors, and then no color is free. The swaps in the sketch of Result 7 are what repair it.