Chordal Graphs, Even‐Hole‐Free Graphs and Sparse Obstructions to Bounded Treewidth
Bibliographic record
Abstract
ABSTRACT Even‐hole‐free graphs pose a central challenge in identifying hereditary classes of bounded treewidth. We investigate this matter by presenting and studying the following conjecture: for an integer and a graph , every even‐hole‐free graph of large enough treewidth has an induced subgraph isomorphic to either or , if (and only if) is a ‐free chordal graph. The “only if” part follows from the properties of the so‐called layered wheels , a construction by Sintiari and Trotignon consisting of (even‐hole, )‐free graphs with arbitrarily large treewidth. Alecu et al. proved recently that the conjecture holds in two special cases: (a) when ; and (b) when for some forest ; that is, is obtained from a forest by adding a universal vertex. Our first result is a common strengthening of (a) and (b): for an integer and graphs and , (even‐hole, )‐free graphs have bounded treewidth if and only if is a forest and is a ‐free chordal graph. Also, for general , we push the current state of the art further than (b) by settling the conjecture for the smallest choices of that are not coned forests. The latter follows from our second result: we prove the conjecture when is a crystal ; that is, a graph obtained from arbitrarily many coned double stars by gluing them together along the “middle” edges of the double stars. In the first version of this paper, we suggested the following which is a strengthening of our main conjecture: for every , every graph of sufficiently large treewidth has an induced subgraph of treewidth which is either complete, complete bipartite, or 2‐degenerate. This strengthening has now been refuted by Chudnovsky and Trotignon [On treewidth and maximum cliques, arxiv:2405.07471 , 2024].
Fetched live from OpenAlex and de-inverted. Abstracts are not stored in this database: the inverted indexes are 8.6 GB of the frame’s 9.3 GB of text, and the host has 13 GB free.
How this classification was reachedexpand
Full frame distilled prediction
Teacher imitationNot calibrated prevalence, not ground truth. Human validation pending. Learned from the 10,348 direct Codex labels and 10,348 direct Gemma labels. Candidate is the union of thresholded teacher heads; consensus is their intersection. These outputs are machine_predicted_unvalidated and are not human labels or direct frontier model labels.
Codex and Gemma teacher scores by category
| Category | Codex | Gemma |
|---|---|---|
| Metaresearch | 0.002 | 0.001 |
| Meta-epidemiology (narrow) | 0.000 | 0.000 |
| Meta-epidemiology (broad) | 0.000 | 0.000 |
| Bibliometrics | 0.003 | 0.003 |
| Science and technology studies | 0.000 | 0.001 |
| Scholarly communication | 0.000 | 0.001 |
| Open science | 0.002 | 0.001 |
| Research integrity | 0.000 | 0.001 |
| Insufficient payload (model declined to judge) | 0.000 | 0.000 |
Machine scores (provisional)
The two teacher heads of the student model, read on this work. A score orders the frame for review; it never asserts a category, and the validation status ships verbatim with every row.
Baseline scores from an immature model (maturity gate not passed, 7 training rounds). Scores rank; they never assert a category.
score_only:v0-immature-baseline · verbatim from the scoring run: score_only means the number may rank works, and no category label ships from itClassification
machine, unvalidatedMachine predicted; a candidate call from one teacher head, not a consensus.
How this classification was reached, model by model and score by score, is at the end of the page under "How this classification was reached".