Triangle-free graphs with arbitrarily large chromatic number

ID: triangle-free-graphs-with-arbitrarily-large-chromatic-number

Define and for . By the Mycielskian chromatic increase and Mycielskian triangle preservation, each is a finite triangle-free graph with chromatic number . The first steps are , the Grötzsch graph, and then a 23-vertex graph needing five colours. The vertex recurrence gives . These explicit examples show how arbitrarily strong graph coloring constraints can accumulate without any three-vertex clique.

New to topics? Read the docs here!