Graph coloring

Vertex, edge, list and fractional colorings of graphs and the chromatic number, from Brooks' and Vizing's theorems to perfect graphs and the four color theorem.

Part 1 of 2

• Centered colorings
• Chromatic number of (0,2)-graphs
• Chromatic number of wheel-free graphs
• Color-critical graphs
• Cycle lengths in graphs of large chromatic number
• Degeneracy and greedy coloring
• Edge coloring
• Four color theorem
• Fractional coloring
• Hajnal–Szemerédi theorem
• Independent sets in graphs of infinite chromatic number
• Kneser graphs
• List coloring
• Odd distance graph
• Perfect graphs
• Petersen coloring conjecture
• Subgraphs of large cochromatic number
• Triangle-free subgraphs of large chromatic number
• Brooks' theorem
• Erdős's theorem on graphs of high girth and high chromatic number

Part 2 of 2

• Five color theorem
• Mycielski's theorem

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.