Pervasiveness of forests of lanterns

Conjecture: every forest of lanterns is pervasive · arXiv:1609.00314

arXiv Informal medium confidence— first stated 2021-05-21

Authors: Maria Chudnovsky, Alex Scott, Paul Seymour

Status open high confidence

The conjecture that every forest of lanterns is pervasive in the class of all graphs remains open. The source paper itself establishes the result for all ρ-controlled ideals (ρ ≥ 2) and for the class of string graphs (which is 2-controlled), but the question for the ideal of all graphs is explicitly noted as open in the abstract. A wide web search through 2026 found no subsequent paper resolving the full conjecture.

Reviewer notes. All five supplied internal references are false positives — none address the forest-of-lanterns pervasiveness conjecture. The conjecture is explicitly open in the source paper for the class of all graphs; the paper's own positive results (ρ-controlled ideals, string graphs) are the deepest known partial results. No follow-up resolving the full conjecture was found in the indexed literature through May 2026.

Auto-reviewed 2026-05-15 with claude-sonnet-4-6 (web search enabled).

Informal. Every forest of lanterns $H$ is pervasive; that is, for all $\nu, \ell \geq 0$ there exists $c$ such that every graph $G$ with $\omega(G) \leq \nu$ and $\chi(G) > c$ contains an induced subgraph isomorphic to an $(\geq \ell)$-subdivision of $H$.

Context

Results of Chalopin, Esperet, Li and Ossona de Mendez (via the Burling/Pawlik graphs) show that every pervasive graph must be a forest of lanterns. The authors state 'perhaps the converse is true, that every forest of lanterns is pervasive', and the abstract notes 'it is not known whether every forest of lanterns is pervasive in the class of all graphs.' The paper proves pervasiveness of all forests of lanterns in every $\rho$-controlled ideal ($\rho \geq 2$) and in the class of string graphs, but the question for the ideal of all graphs remains open.

Notes. Stated as 'perhaps the converse is true' in the introduction and as an explicitly open problem in the abstract; no formal conjecture environment.

Source paper

Induced subgraphs of graphs with large chromatic number. V. Chandeliers and strings
Maria Chudnovsky, Alex Scott, Paul Seymour · 2021-05-21
https://arxiv.org/abs/1609.00314 PDF source