Chromatic Number

Graph Theory · Axiom Academy

Understanding the minimum number of colors needed to properly color a graph 1. Definition and Basic Bounds Definition: The chromatic number of a graph G, denoted by χ(G), is the minimum number k such that G has a proper k-coloring. A proper k-coloring assigns one of k colors to each vertex such that adjacent vertices receive different colors. Where n is the number of vertices in G. Every graph can be colored with at most n colors (assign each vertex a unique color), and requires at least 1 color (empty graph or single vertex). Several important characterizations help us determine chromatic numbers for specific graph types: Empty or Edgeless Graphs: χ(G) = 1 if and only if G has no edges (each vertex can have the same color) Bipartite Graphs: χ(G) = 2 if and only if G is bipartite and has at least one edge Complete Graphs: χ(K_n) = n (every pair of vertices is adjacent, so all need different colors) 3. Clique Number as Lower Bound The clique number ω(G) is the size of the largest complete subgraph in G. Since all vertices in a clique must receive different colors, we have: This provides a lower bound on the chromatic number. However, the chromatic number can be much larger than the clique number. For example, cycle graphs with odd length n have ω(C_n) = 2 but χ(C_n) = 3. 4. Finding Chromatic Numbers: Examples Let's examine how to determine the chromatic number of different graphs through visual analysis: Identify any complete subgraphs to establish a lower bound

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