Editing Circle graph (section)

==Chromatic number==
[[File:Ageev 5X circle graph.svg|thumb|left|300px|The chords forming the 220-vertex 5-chromatic triangle-free circle graph of {{harvtxt|Ageev|1996}}, drawn as an [[arrangement of lines]] in the 
[[Hyperbolic space|hyperbolic plane]].]]
The [[chromatic number]] of a circle graph is the minimum number of colors that can be used to color its chords so that no two crossing chords have the same color. Since it is possible to form circle graphs in which arbitrarily large sets of chords all cross each other, the chromatic number of a circle graph may be arbitrarily large, and determining the chromatic number of a circle graph is NP-complete.{{sfnp|Garey|Johnson|Miller|Papadimitriou|1980}} It remains NP-complete to test whether a circle graph can be colored by four colors.{{sfnp|Unger|1988}} {{harvtxt|Unger|1992}} claimed that finding a coloring with three colors may be done in [[polynomial time]] but his writeup of this result omits many details.{{sfnp|Unger|1992}}

Several authors have investigated problems of coloring restricted subclasses of circle graphs with few colors. In particular, for circle graphs in which no sets of ''k'' or more chords all cross each other, it is possible to color the graph with as few as <math>7k^2</math> colors. One way of stating this is that the circle graphs are [[χ-bounded|<math>\chi</math>-bounded]].<ref>{{harvtxt|Davies|McCarty|2021}}. For earlier bounds see {{harvtxt|Černý|2007}}, {{harvtxt|Gyárfás|1985}}, {{harvtxt|Kostochka|1988}}, and {{harvtxt|Kostochka|Kratochvíl|1997}}.</ref> In the particular case when ''k''&nbsp;=&nbsp;3 (that is, for [[triangle-free graph|triangle-free]] circle graphs) the chromatic number is at most five, and this is tight: all triangle-free circle graphs may be colored with five colors, and there exist triangle-free circle graphs that require five colors.<ref>See {{harvtxt|Kostochka|1988}} for the upper bound, and {{harvtxt|Ageev|1996}} for the matching lower bound. {{harvtxt|Karapetyan|1984}} and {{harvtxt|Gyárfás|Lehel|1985}} give earlier weaker bounds on the same problem.</ref> If a circle graph has [[girth (graph theory)|girth]] at least five (that is, it is triangle-free and has no four-vertex cycles) it can be colored with at most three colors.<ref>{{harvtxt|Ageev|1999}}.</ref> The problem of coloring triangle-free squaregraphs is equivalent to the problem of representing [[squaregraph]]s as isometric subgraphs of [[Cartesian product of graphs|Cartesian products]] of [[Tree (graph theory)|trees]]; in this correspondence, the number of colors in the coloring corresponds to the number of trees in the product representation.{{sfnp|Bandelt|Chepoi|Eppstein|2010}}