Bounded tree-independence conjecture for (even hole, diamond)-free graphs

About 3 years old · traced to

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 tree-α⁡(G)\operatorname{tree-\alpha}(G). 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

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.