Vertex Coloring

Graph Theory · Axiom Academy

Understanding proper vertex coloring, k-colorings, and the connection to independent sets In simple terms: adjacent vertices must receive different colors. The animation below shows a graph being properly colored step by step. Key Observation: The constraint applies only to adjacent vertices. Non-adjacent vertices can share the same color. 2. k-Coloring and k-Colorable Graphs The minimum number of colors needed to properly color a graph is called its chromatic number , denoted χ(G). Complete graphs: χ(K_n) = n (every vertex needs a different color) Bipartite graphs: χ(G) = 2 (two colors suffice) Cycle graphs: χ(C_n) = 2 if n is even, 3 if n is odd 3. Coloring as Partitioning into Independent Sets Each color class (all vertices assigned the same color) forms an independent set. Conversely, any partition of V into independent sets gives a proper coloring. Equivalence: Finding a k-coloring is equivalent to partitioning vertices into k independent sets. 4. Coloring Different Graph Types Different graph structures require different numbers of colors. Let's examine how various graph types are colored.

This is the written version of the interactive lesson above. See the full Graph Theory course.