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!