fvs–face-packing ratio in planar graphs

AX_planar_fvs_face_packing_ratio_2

Source: arXiv:1912.01570 — Jones' Conjecture in subcubic graphs

Conjecture 2 · arXiv:1912.01570

arXiv Conjecture high confidence— first stated 2019-12-03

Authors: Marthe Bonamy, François Dross, Tomáš Masařík, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk

Status ai-disproved high confidence

A 12-vertex planar graph has fvs = 5 and fp = 2; a related family has fvs/fp tending to 3.

Cited literature (1)

partial Jones' conjecture for Halin graphs and a bit more (2024)

unknown · arXiv preprint · arXiv:2401.07376

Proves Jones' conjecture (fvs ≤ 2·cp) for Halin graphs and based planar graphs, but addresses cycle-packing (cp) rather than face-packing (fp), so does not directly settle Conjecture 2.

Auto-reviewed 2026-09-16 with gpt-6-astra.

AI-generated write-up ai-disproved

Open the PDF write-up

This is a model-generated research artifact, not a peer-reviewed publication or a formally verified proof.

Conjecture. For every planar graph $G$, we have $\mathrm{fvs}(G) \leq 2 \cdot \mathrm{fp}(G)$, where $\mathrm{fp}(G)$ is the maximum size of a face-packing of $G$, i.e., a cycle-packing where, for some embedding of $G$, every cycle bounds a face.

Context

The authors pose this stronger conjecture to highlight how little is understood around Jones' Conjecture. They note that the example of many nested disjoint cycles shows the embedding cannot be fixed, and that the simple discharging argument giving $\mathrm{fvs}(G) \leq 3\,\mathrm{cp}(G)$ does not imply this conjecture even with factor 3 instead of 2.

Source paper

Jones' Conjecture in subcubic graphs
Marthe Bonamy, François Dross, Tomáš Masařík, Wojciech Nadara, Marcin Pilipczuk, Michał Pilipczuk · 2019-12-03
https://arxiv.org/abs/1912.01570 PDF source