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

For a graph G=(V(G),E(G))G=(V(G),E(G)), let tw(G)\operatorname{tw}(G) denote its treewidth, defined as the minimum width of a tree decomposition, where the width is the maximum bag size minus one. A hole is an induced cycle with at least four vertices, and an even-hole-free graph has no hole of even length. A clique is a set of pairwise adjacent vertices. Sintiari and Trotignon's conjecture. For every integer tt, there exists a constant ctc_t such that every even-hole-free graph GG with no clique of size tt satisfies

tw(G)ctlogV(G).\operatorname{tw}(G)\leq c_t\log |V(G)|.

This conjecture seeks a logarithmic upper bound on treewidth in terms of the number of vertices for even-hole-free graphs with bounded clique number, reflecting the paper's aim of establishing logarithmic treewidth under such structural restrictions. Its resolution status is not specified in the supplied source material.

Sources & referencesView supporting material

Primary source

Tara Abrishami, Bogdan Alecu, Maria Chudnovsky, Sepehr Hajebi and Sophie Spirkl, “Induced subgraphs and tree decompositions X. Towards logarithmic treewidth for even-hole-free graphs”, arXiv:2307.13684 (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.