Polynomial chi-boundedness conjecture for path-free graphs

From papers

For a graph GG, let χ(G)\chi(G) denote its chromatic number and let ω(G)\omega(G) denote its clique number. A graph is PP-free if it contains no induced copy of the path PP. Path-free polynomial chi-boundedness conjecture. For every integer kk, there is a constant Ck>0C_k>0 such that every graph GG satisfying

χ(G)ω(G)Ck\chi(G)\geq \omega(G)^{C_k}

contains an induced path of length kk. 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 P5P_5-free graphs, while the stated polynomial form remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

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.

Solutions 0

No solutions have been posted yet.