Sintiari and Trotignon's diamond conjecture for even-hole-free graphs

Let a diamond be the graph obtained from a two-edge path by adding a universal vertex. Consider graphs with no induced even hole and no induced K4K_4.

Sintiari and Trotignon's conjecture. Every (even-hole, K4K_4)-free graph of sufficiently large treewidth contains a diamond as an induced subgraph.

This conjecture was posed because the graphs in the paper's construction have many induced diamonds. It is solved by the paper's main theorem, which proves the stronger characterization that a graph HH occurs in every sufficiently large-treewidth (even-hole, K4K_4)-free graph exactly when HH is a K4K_4-free chordal graph.

Sources & referencesView supporting material

Primary source

Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi and Sophie Spirkl, “Induced subgraphs and tree decompositions XI. Local structure in even-hole-free graphs of large treewidth”, arXiv:2309.04390 (2025).

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.