Bounded tree-independence conjecture for (even hole, diamond)-free graphs
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.
Sources & referencesView supporting material
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
Sign in to submit a solution.
No solutions have been posted yet.