Gyárfás's conjecture on chi-boundedness of forest-free graphs

About 13 years old · traced to

Let HH be a fixed forest, and let G(H)\mathcal{G}(H) denote the hereditary class of graphs with no induced subgraph isomorphic to HH. A graph class is chi-bound if there is a function ff such that χ(G)≤f(ω(G))\chi(G)\leq f(\omega(G)) for every graph GG in the class, where χ(G)\chi(G) is the chromatic number and ω(G)\omega(G) is the clique number. Gyárfás's conjecture. The class G(H)\mathcal{G}(H) is chi-bound for every fixed forest HH. 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

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.