Gyárfás's conjecture on chi-boundedness of forest-free graphs
Let be a fixed forest, and let denote the hereditary class of graphs with no induced subgraph isomorphic to . A graph class is chi-bound if there is a function such that for every graph in the class, where is the chromatic number and is the clique number. Gyárfás's conjecture. The class is chi-bound for every fixed forest . This conjecture asks whether forbidding any fixed induced forest yields a bounded relationship between chromatic number and clique number; it is presented as an open problem in the source's discussion of Gyárfás's conjectures.
References
Primary source
Athmakoori Prashant, S. Francis Raj and M. Gokulnath, “Linear χ-binding functions for \P_3P_2, gem\-free graphs”, arXiv:2305.11757 (2023).
Additional references
6 papers in this index state this conjecture (2013–2023). The statement above is taken from the most recent of them; the others are arXiv:2102.13458, arXiv:1807.05547, arXiv:1512.03481, arXiv:1308.6678, arXiv:1301.5149.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.