Χ-bounded

In graph theory, a -bounded family of graphs is one for which there is some function such that, for every integer the graphs in with (clique number) can be colored with at most colors. This concept and its notation were formulated by András Gyárfás. The use of the Greek letter chi in the term -bounded is based on the fact that the chromatic number of a graph is commonly denoted . It is not true that the family of all graphs is -bounded. As and showed, there exist triangle-free graphs of arbitrarily large chromatic number, so for these graphs it is not possible to define a finite value of . Thus, -boundedness is a nontrivial concept, true for some graph families and false for others. Every class of graphs of bounded chromatic number is (trivially) -bounded, with 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 -bounded, with . The claw-free graphs more generally are also -bounded with . 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, . Other -bounded graph families include: The perfect graphs, with The graphs of boxicity two, which is the intersection graphs of axis-parallel rectangles, with (big O notation) The graphs of bounded clique-width The intersection graphs of scaled and translated copies of any compact convex shape in the plane The polygon-circle graphs, with The circle graphs, with 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 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 The intersection graphs of curves that cross a fixed curve between 1 and times 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 -bounded.