of graphs is one for which there is some function
(clique number) can be colored with at most
These concepts and their notations were formulated by András Gyárfás.
[1] The use of the Greek letter chi in the term
-bounded is based on the fact that the chromatic number of a graph
An overview of the area can be found in a survey of Alex Scott and Paul Seymour.
[2] It is not true that the family of all graphs is
As Descartes (1947), Zykov (1949) and Mycielski (1955) showed, there exist triangle-free graphs of arbitrarily large chromatic number,[3][4][5] so for these graphs it is not possible to define a finite value of
-boundedness is a nontrivial concept, true for some graph families and false for others.
[6] Every class of graphs of bounded chromatic number is (trivially)
equal to the bound on the chromatic number.
This includes, for instance, the planar graphs, the bipartite graphs, and the graphs of bounded degeneracy.
Complementarily, the graphs in which the independence number is bounded are also
-bounded, as Ramsey's theorem implies that they have large cliques.
Vizing's theorem can be interpreted as stating that the line graphs are
[7][8] The claw-free graphs more generally are also
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,
-bounded graph families include: 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
They include as a special case the intersection graphs of line segments, which are also not
[6] According to the Gyárfás–Sumner conjecture, for every tree
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.
-bounded class of graphs is polynomially
that grows at most polynomially as a function of
contains an independent set with cardinality at least
-boundedness was posed by Louis Esperet, who asked whether every hereditary class of graphs that is
[8] A strong counterexample to Esperet's conjecture was announced in 2022 by Briański, Davies, and Walczak, who proved that there exist
-bounded hereditary classes whose function
can be chosen arbitrarily as long as it grows more quickly than a certain cubic polynomial.