Bounded tree-independence conjecture for (even hole, diamond)-free graphs
An (even hole, diamond)-free graph is a graph containing neither an even hole nor a diamond as an induced subgraph. Its tree independence number is denoted by . Bounded tree-independence conjecture. The class of (even hole, diamond)-free graphs has bounded tree independence number. The conjecture would extend the polynomial-time maximum weight independent set result established in the paper to a larger class; the source says that this remains open.
References
Primary source
Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi, Sophie Spirkl and Kristina Vušković, “Tree independence number I. (Even hole, diamond, pyramid)-free graphs”, arXiv:2305.16258 (2024).
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.