Graph-theory open problems

fvs–face-packing ratio in planar 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 open medium confidence

Conjecture 2 from arXiv:1912.01570 — that fvs(G) ≤ 2·fp(G) for every planar graph G — is a strengthening of Jones' conjecture (the cp-version fvs ≤ 2·cp) and appears to remain open. Related progress since 2019 concerns Jones' conjecture itself (cycle-packing, not face-packing): arXiv:2401.07376 (2024) proves fvs ≤ 2·cp for Halin graphs and 'based planar graphs,' but since fp(G) ≤ cp(G), this does not imply the face-packing conjecture. No paper resolving Conjecture 2 was found in the indexed literature.

Cited literature (1)

Reviewer notes. Conjecture 2 (fvs ≤ 2·fp) is strictly stronger than Jones' conjecture (fvs ≤ 2·cp) because any face-packing is a cycle-packing so fp(G) ≤ cp(G). The best known general bound remains fvs(G) ≤ 3·cp(G). The 2401.07376 paper (2024) makes progress on Jones' conjecture for special graph classes but not on the face-packing variant. Author names for 2401.07376 could not be confirmed from the fetched abstract page.

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

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