Editing Graph coloring (section)

=== Graphs with high chromatic number ===
Graphs with large [[Clique (graph theory)|cliques]] have a high chromatic number, but the opposite is not true. The [[Grötzsch graph]] is an example of a 4-chromatic graph without a triangle, and the example can be generalized to the [[Mycielskian]]s.
: '''Theorem''' ({{harvard citations|nb|first=William T.|last=Tutte|year=1947|author-link=W. T. Tutte}},{{sfnp|Descartes|1947}} {{harvard citations|nb|first=Alexander|last=Zykov|year=1949|author-link=Alexander Zykov}}, {{harvard citations|nb|first=Jan|last=Mycielski|year=1955|author-link=Jan Mycielski}}): There exist triangle-free graphs with arbitrarily high chromatic number.

To prove this, both, Mycielski and Zykov, each gave a construction of an inductively defined family of [[triangle-free graph]]s but with arbitrarily large chromatic number.{{sfnp|Scott|Seymour|2020}} {{harvtxt|Burling|1965}} constructed axis aligned boxes in <math>\mathbb{R}^{3}</math> whose [[intersection graph]] is triangle-free and requires arbitrarily many colors to be properly colored. This family of graphs is then called the Burling graphs. The same class of graphs is used for the construction of a family of triangle-free line segments in the plane, given by Pawlik et al. (2014).{{sfnp|Pawlik|Kozik|Krawczyk|Lasoń|2014}} It shows that the chromatic number of its intersection graph is arbitrarily large as well. Hence, this implies that axis aligned boxes in <math>\mathbb{R}^{3}</math> as well as line segments in <math>\mathbb{R}^{2}</math> are not [[χ-bounded|''χ''-bounded]].{{sfnp|Pawlik|Kozik|Krawczyk|Lasoń|2014}}

From Brooks's theorem, graphs with high chromatic number must have high maximum degree. But colorability is not an entirely local phenomenon: A graph with high [[Girth (graph theory)|girth]] looks locally like a tree, because all cycles are long, but its chromatic number need not be 2:
: '''Theorem''' ([[Paul Erdős|Erdős]]): There exist graphs of arbitrarily high girth and chromatic number.{{sfnp|Erdős|1959}}