Sintiari–Trotignon conjecture on treewidth of diamond-free even-hole-free graphs

For a graph GG, let tw(G)\operatorname{tw}(G) denote its treewidth. A graph is even-hole-free if it has no induced cycle of even length at least four, and the diamond is the graph on four vertices with five edges. Sintiari–Trotignon's conjecture. For every integer t1t\geq 1, there exists a constant ctc_t such that every even-hole-free graph GG with no induced diamond and no clique of size tt satisfies

tw(G)ct.\operatorname{tw}(G)\leq c_t.

This conjecture was resolved in the cited work TWXI, so the asserted bounded-treewidth conclusion is now a theorem.

Sources & referencesView supporting material

Primary source

Maria Chudnovsky, Peter Gartland, Sepehr Hajebi, Daniel Lokshtanov and Sophie Spirkl, “Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth”, arXiv:2402.14211 (2024).

Additional references

2 papers in this index state this conjecture (2022–2024). The statement above is taken from the most recent of them; the others are arXiv:2203.06775.

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.