The even-hole-free graph and K4-free chordal graph conjecture

Let t4t\geq 4 be an integer, let HH be a graph, and call HH K4K_4-free chordal if it is chordal and contains no induced subgraph isomorphic to K4K_4. An even-hole-free graph has no induced cycle of even length at least four, and tw(G)\operatorname{tw}(G) denotes the treewidth of GG. The even-hole-free graph and K4-free chordal graph conjecture. For every t4t\geq 4 and every K4K_4-free chordal graph HH, every even-hole-free graph of sufficiently large treewidth has an induced subgraph isomorphic to KtK_t or HH. This is the paper's main conjecture; it is known for t=4t=4, for coned forests, and for crystals, but remains open in general.

Sources & referencesView supporting material

Primary source

Sepehr Hajebi, “Chordal graphs, even-hole-free graphs and sparse obstructions to bounded treewidth”, arXiv:2401.01299 (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.