The 2-forest conjecture for even-hole-free graphs

For an integer k1k\geq 1, a kk-forest is a Kk+2K_{k+2}-free chordal graph; in particular, a 22-forest is a K4K_4-free chordal graph. An even-hole-free graph has no induced cycle of even length at least four, and an (F)(\mathcal{F})-free graph contains no induced subgraph isomorphic to a graph in F\mathcal{F}. The 2-forest conjecture. Given an integer t4t\geq 4 and a 22-forest HH, every ((even-hole,Kt),K_t)-free graph of sufficiently large treewidth contains HH if and only if HH is a 22-forest. The only-if direction follows from layered wheels; the substantive if direction is the main open question and is equivalent to the paper's main conjecture.

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.