Polynomial chi-boundedness conjecture for path-free graphs

About 6 years old · traced to

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.

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

Never refreshed

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.