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 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.

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

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.