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

About 2 years old · traced to

Let t≥4t\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 t≥4t\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.

References

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.