Induced 2-degenerate ⅞ subgraph triangle-free planar

Conjecture 1.1 · arXiv:1709.04036

arXiv Conjecture high confidence— first stated 2018-02-19

Authors: Zdeněk Dvořák, Tom Kelly

Status open high confidence

Conjecture 1.1 from arXiv:1709.04036 — that every triangle-free planar graph contains an induced 2-degenerate subgraph on at least 7/8 of its vertices — remains open. The source paper itself provides the best known partial progress: an unconditional 4/5 bound (Theorem 1.2) and a 7/8n − 18n_3 bound (Theorem 1.3) where n_3 is the number of low-degree vertices. A broad web search across subsequent literature (through May 2026) found no paper proving or disproving the full 7/8 bound.

Reviewer notes. No follow-up paper resolving the conjecture was found. Related work on induced k-degenerate subgraphs of planar graphs (e.g., arXiv:2002.07984 on 3-degenerate subgraphs, arXiv:2511.13693 on sparse graphs) cites the 4/5 bound from this paper but does not improve the 2-degenerate triangle-free planar bound. The conjecture is tight for the 3-cube graph (unique 3-regular triangle-free planar graph on 8 vertices).

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

Conjecture. Every triangle-free planar graph contains an induced 2-degenerate subgraph on at least $\frac{7}{8}$ of its vertices.

Context

The authors introduce this as the central open problem motivating the paper, noting it would be tight for the cube (the unique 3-regular triangle-free planar graph on 8 vertices). The paper's main theorems (Theorems 1.2 and 1.3) prove weaker bounds of $\frac{4}{5}$ and $\frac{7}{8}n - 18n_3$ respectively as partial progress.

Source paper

Induced 2-degenerate Subgraphs of Triangle-free Planar Graphs
Zdeněk Dvořák, Tom Kelly · 2018-02-19
https://arxiv.org/abs/1709.04036 PDF source