Thin overlays without bounded-degree assumption

Informal Conjecture (Section 1.2): dropping bounded-degree assumption · arXiv:1704.00125

arXiv Informal medium confidence— first stated 2017-04-01

Status open low confidence

No verified follow-up paper has been found that resolves the conjecture that the bounded-maximum-degree assumption can be dropped from the result that subgraph-closed graph classes with strongly sublinear separators admit thin systems of overlays. The conjecture is from 2017 and is thus old enough that the absence of evidence in a web search is suspicious. A 2022 paper (arXiv:2208.10074) characterises hereditary graph classes with strongly sublinear separators structurally (as subgraphs of strong products of a star and a complete graph) but could not be confirmed to address the thin-overlay conjecture directly.

Reviewer notes. Web search found two potentially related papers: arXiv:2208.10074 (Dujmović et al., 2022, 'Product structure of graph classes with strongly sublinear separators') and arXiv:2103.08698 (Dvořák, 2021, 'Approximation metatheorems for classes with bounded expansion'). The 2208.10074 abstract discusses hereditary classes with strongly sublinear separators but does not mention thin systems of overlays. The 2103.08698 paper generalises PTAS results to bounded-expansion classes (a stronger assumption than sublinear separators), so it does not settle the conjecture of dropping bounded degree. No paper directly proving or disproving the conjecture was found within the 5-call cap; status is open with low confidence given the 9-year age of the conjecture.

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

Informal. It seems plausible that this additional assumption [bounded maximum degree] could be dropped, leading to a much more general result strengthening majority of the algorithms mentioned in the previous subsection.

Context

The paper proves that subgraph-closed graph classes with strongly sublinear separators admit thin systems of overlays under the additional assumption that their maximum degree is bounded. The authors conjecture this extra condition is unnecessary, which would subsume a much wider class of results.

Notes. Stated informally in the 'Limitations of our technique' subsection; no labelled theorem environment.

Source paper

Thin graph classes and polynomial-time approximation schemes
Zdeněk Dvořák · 2017-04-01
https://arxiv.org/abs/1704.00125 PDF source