Sintiari and Trotignon's logarithmic-treewidth conjecture for even-hole-free graphs
Sintiari and Trotignon's logarithmic-treewidth conjecture for even-hole-free graphs
For a graph , let 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 , there exists a constant such that every even-hole-free graph with no clique of size satisfies
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.