Χ-bounded: Difference between revisions

In graph theory, a ${\displaystyle \chi }$-bounded family ${\displaystyle {\mathcal {F}}}$ of graphs is one for which there is some function ${\displaystyle f}$ such that, for every integer ${\displaystyle t}$ the graphs in ${\displaystyle {\mathcal {F}}}$ with ${\displaystyle t=\omega (G)}$ (

with at most ${\displaystyle f(t)}$ colors. This concept and its notation were formulated by András Gyárfás.^[1] The use of the Greek letter chi in the term ${\displaystyle \chi }$-bounded is based on the fact that the of a graph ${\displaystyle G}$ is commonly denoted ${\displaystyle \chi (G)}$.

Nontriviality

It is not true that the family of all graphs is ${\displaystyle \chi }$-bounded. As Zykov (1949) and Mycielski (1955) showed, there exist triangle-free graphs of arbitrarily large chromatic number,^[2][3] so for these graphs it is not possible to define a finite value of ${\displaystyle f(2)}$. Thus, ${\displaystyle \chi }$-boundedness is a nontrivial concept, true for some graph families and false for others.^[4]

Specific classes

Every class of graphs of bounded

is (trivially) ${\displaystyle \chi }$-bounded, with ${\displaystyle f(t)}$ equal to the bound on the chromatic number. This includes, for instance, the is bounded are also ${\displaystyle \chi }$-bounded, as Ramsey's theorem implies that they have large cliques.

Vizing's theorem can be interpreted as stating that the line graphs are ${\displaystyle \chi }$-bounded, with ${\displaystyle f(t)=t+1}$.^[5][6] The claw-free graphs more generally are also ${\displaystyle \chi }$-bounded with ${\displaystyle f(t)\leq t^{2}}$. This can be seen by using Ramsey's theorem to show that, in these graphs, a vertex with many neighbors must be part of a large clique. This bound is nearly tight in the worst case, but connected claw-free graphs that include three mutually-nonadjacent vertices have even smaller chromatic number, ${\displaystyle f(t)=2t}$.^[5]

Other ${\displaystyle \chi }$-bounded graph families include:

• The perfect graphs, with ${\displaystyle f(t)=t}$
• The graphs of boxicity two^[7], which is the intersection graphs of axis-parallel rectangles, with ${\displaystyle f(t)\in O(t\log(t))}$(big O notation)^[8]
• The graphs of bounded clique-width^[9]
• The intersection graphs of scaled and translated copies of any compact convex shape in the plane^[10]
• The polygon-circle graphs, with ${\displaystyle f(t)=2^{t}}$
• The circle graphs, with ${\displaystyle f(t)=7t^{2}}$^[11] and (generalizing circle graphs) the "outerstring graphs", intersection graphs of bounded curves in the plane that all touch the unbounded face of the arrangement of the curves^[12]
• The outerstring graph is an intersection graph of curves that lie in a common half-plane and have one endpoint on the boundary of that half-plane^[13]
• The intersection graphs of curves that cross a fixed curve between 1 and ${\displaystyle n\in \mathbb {N} }$ times^[14]

However, although intersection graphs of convex shapes, circle graphs, and outerstring graphs are all special cases of string graphs, the string graphs themselves are not ${\displaystyle \chi }$-bounded. They include as a special case the intersection graphs of line segments, which are also not ${\displaystyle \chi }$-bounded.^[4]

Unsolved problems

According to the Gyárfás–Sumner conjecture, for every tree ${\displaystyle T}$, the graphs that do not contain ${\displaystyle T}$ as an induced subgraph are ${\displaystyle \chi }$-bounded. For instance, this would include the case of claw-free graphs, as a claw is a special kind of tree. However, the conjecture is known to be true only for certain special trees, including paths^[1] and radius-two trees.^[15]

Another problem on ${\displaystyle \chi }$-boundedness was posed by Louis Esperet, who asked whether every hereditary class of graphs that is ${\displaystyle \chi }$-bounded has a function ${\displaystyle f(t)}$ that grows at most polynomially as a function of ${\displaystyle t}$.^[6] A strong counterexample to Esperet's conjecture was announced in 2022 by Briański, Davies, and Walczak, who proved that there exist ${\displaystyle \chi }$-bounded hereditary classes whose function ${\displaystyle f(t)}$ can be chosen arbitrarily as long as it grows more quickly than a certain cubic polynomial.^[16]

References

External links

• Chi-bounded, Open Problem Garden