TOPICS
Search

Gyárfás-Sumner Conjecture


The Gyárfás-Sumner conjecture asserts that for each fixed tree T, the class of graphs with no induced subgraph isomorphic to T is a chi-bounded graph class (Sumner 1981, Gyárfás 1987). Equivalently, for every positive integer k there is a bound depending only on T and k on the chromatic number of any such graph with clique number at most k.

The conjecture holds when T is a path graph, a star graph, or a tree of graph radius at most 2 (Scott and Seymour 2020). The conjecture is equivalent to the corresponding statement for every forest, since every forest is an induced subgraph of a tree.


See also

Chi-Bounded Graph Class, Induced Subgraph, Tree

Explore with Wolfram|Alpha

References

Gyárfás, A. "Problems from the World Surrounding Perfect Graphs." Appl. Math. (Warsaw) 19, 413-441, 1987.Scott, A. and Seymour, P. "A Survey of chi-Boundedness." J. Graph Th. 95, 473-504, 2020. https://doi.org/10.1002/jgt.22601.Sumner, D. P. "Subtrees of a Graph and the Chromatic Number." In The Theory and Applications of Graphs (Ed. G. Chartrand). New York: Wiley, pp. 557-576, 1981.

Cite this as:

Weisstein, Eric W. "Gyárfás-Sumner Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Gyarfas-SumnerConjecture.html

Subject classifications