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.
Articles by others on the same topic
There are currently no matching articles.