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

About 3 years old · traced to

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)≤ctlog⁡∣V(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.

References

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.