Sintiari and Trotignon's diamond conjecture for even-hole-free graphs
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 .
Sintiari and Trotignon's conjecture. Every (even-hole, )-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 occurs in every sufficiently large-treewidth (even-hole, )-free graph exactly when is a -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
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.