Polynomial chi-boundedness conjecture for path-free graphs
For a graph , let denote its chromatic number and let denote its clique number. A graph is -free if it contains no induced copy of the path . Path-free polynomial chi-boundedness conjecture. For every integer , there is a constant such that every graph satisfying
contains an induced path of length . Equivalently, for every fixed path, the class of graphs excluding that path as an induced subgraph is polynomially chi-bounded. The general chi-boundedness of path-free classes is known only in limited cases; the paper notes a bound for -free graphs, while the stated polynomial form remains open.
References
Primary source
António Girão and Zach Hunter, “Induced subdivisions in K_s,s-free graphs with polynomial average degree”, arXiv:2310.18452 (2024).
Additional references
2 papers in this index state this conjecture (2020–2023). The statement above is taken from the most recent of them; the others are arXiv:2003.12960.
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.