--- ## Definition > [!tldr] Definition > The **chromatic number** of a [[graph]] $G$ is the minimum number of colors in any proper [[Vertex coloring|vertex coloring]] of $G$. The chromatic number of $G$ is denoted $\chi(G)$. Notes - $\chi$ is the Greek letter "chi", pronounced "Kie" (rhymes with "pie"). - A given graph can have many different possible proper [[Vertex coloring|colorings]]; for example we can just assign a different color to each vertex. But there is only one minimum number of colors needed for a proper coloring, and that number is $\chi(G)$. - The [[Greedy coloring algorithm|greedy graph coloring]] algorithm can, but does not always produce the minimum coloring. ## Examples **Example 1 -- Complete graphs** The chromatic number of $K_3$, the [[Complete graph|complete graph]] on three vertices, is $3$. Since each vertex is [[adjacent]] to the other two, three colors are necessary for a proper coloring, and two colors are not enough: ![[colored-k3.png|400]] By extension, $\chi(K_n) = n$ (where $K_n$ is the [[Complete graph|complete graph]] on $n$ vertices) for every positive [[Integers|integer]] $n$, since each vertex is [[adjacent]] to the remaining $n-1$ vertices. Also by extension, any graph that has $K_3$ (a triangle) as a [[Subgraph|subgraph]] must have a chromatic number greater than or equal to 3, since a minimum of 3 colors is required to color just the triangle. It can be proven as a [[theorem]] that the chromatic number of a graph is always greater than or equal to its [[Clique number|clique number]] (the largest value of $n$ for which the graph has a [[Subgraph|subgraph]] that is [[Isomorphism|isomorphic]] to the [[Complete graph|complete graph]] $K_n$). The graph below has a chromatic number of 4; a 4-coloring is shown. While there are proper colorings of this graph with more than four colors (again we could just assign 11 different colors, one for each vertex) there are no proper colorings with 3 or fewer colors: ![[grotzschgraph.png]] **Example 2: A [[path graph]] $P_4$** Consider the [[path graph]] on 4 vertices: $v_1 - v_2 - v_3 - v_4$. - Assign color 1 to $v_1$, color 2 to $v_2$, color 1 to $v_3$, color 2 to $v_4$. - No two adjacent vertices share a color. ✓ - Can we do it with just 1 color? No — adjacent vertices would share the same color. ✗ - So $\chi(P_4) = 2$. In fact, any path graph $P_n$ (with $n \geq 2$) has $\chi(P_n) = 2$, since path graphs contain no odd cycles. **Example 3: A cycle graph $C_5$** Consider the 5-cycle: $v_1 - v_2 - v_3 - v_4 - v_5 - v_1$. - Try 2 colors: alternate 1, 2, 1, 2, 1. But then $v_5$ (color 1) is adjacent to $v_1$ (color 1) — conflict! ✗ - With 3 colors: assign 1, 2, 1, 2, 3. Now $v_5$ (color 3) is adjacent to $v_4$ (color 2) and $v_1$ (color 1) — no conflicts. ✓ - So $\chi(C_5) = 3$. This illustrates a key fact: **[[Even and odd integers|odd]] [[Paths|cycles]] require 3 colors**. Even [[Paths|cycles]] (like $C_4$, $C_6$, ...) only require 2. ## Resources  ### Practice **Problem 1.** For each graph below, find the chromatic number and explain your reasoning. (a) The [[cycle graph]] $C_6$ (b) The [[Bipartite graph|complete bipartite graph]] $K_{2,3}$ (c) The [[complete graph]] $K_5$ (d) A graph with 5 vertices where vertex $A$ is connected to $B$, $C$, and $D$; vertex $B$ is connected to $C$; and vertex $E$ is isolated (connected to no one). --- **Problem 2.** A scheduling problem: Five student groups need to present, but groups that share a member cannot present at the same time. The conflicts are: - Groups 1 and 2 share a member - Groups 1 and 3 share a member - Groups 2 and 4 share a member - Groups 3 and 4 share a member - Groups 3 and 5 share a member Model this as a graph coloring problem and find the minimum number of time slots needed. Justify your answer. --- **Problem 3.** Apply the [[greedy coloring algorithm]] to the graph from Problem 1(d) using two different orderings of the vertices. Do both orderings achieve the chromatic number? What does this tell you about the greedy algorithm? --- **Problem 4 (Challenge).** Prove that $\chi(G) = 2$ [[Biconditional statement|if and only if]] $G$ is a [[bipartite graph]] with at least one edge. (Hint: argue both directions of the "[[Biconditional statement|if and only if]]".)