Bridge path-elongation structure of ℓ(G)+br(G) counterexamples

Open question on counter-examples to ℓ(G)+br(G)≥|G| · arXiv:1606.06011

arXiv Informal medium confidence— first stated 2016-06-20

Authors: Pierre Aboulker, Martin Matamala, Paul Rochet, Jose Zamora

Status open medium confidence

The structural question of whether all counter-examples to $\ell(G)+\mathrm{br}(G)\geq|G|$ arise, up to bridge-to-path replacement, from a finite base set of graphs remains unresolved in the published literature found. Subsequent work has characterised counter-examples in restricted graph classes (bipartite graphs by Matamala and Zamora 2020, locally connected and diameter-2 graphs circa 2025) and proved the Chen-Chvátal conjecture for graphs of diameter three (arXiv:2512.12047), but none of these results directly address the bridge-elongation characterisation question posed in the source paper.

Cited literature (1)

partial Chen-Chvátal Conjecture for Graphs of Diameter 3 (2025)

not confirmed from abstract fetch · arXiv preprint · arXiv:2512.12047

Proves that all graphs of diameter three satisfy the Chen-Chvátal conjecture by classifying all such graphs having fewer lines than vertices; does not directly address the bridge path elongation characterisation of counter-examples.

Reviewer notes. The 2020 paper 'Lines in bipartite graphs and in 2-metric spaces' by Matamala and Zamora (J. Graph Theory 94(5):565–585) characterises all bipartite counter-examples to the inequality and is likely the closest related work, but its URL was not WebFetched and it is not included in since_posted. Similarly, 2025 preprints characterising counter-examples for locally connected and diameter-2 graphs were identified in search summaries but not individually verified. No paper that directly resolves the bridge path elongation question was found.

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

Informal. It remains unknown whether all counter-examples to $\ell(G) + \mathrm{br}(G) \geq |G|$ can be obtained from a finite set of graphs by replacing a bridge by a path of arbitrary length.

Context

The authors note (on the basis of an observation by Yori Zwols) that any counter-example containing a bridge generates infinitely many counter-examples by path-elongation. They ask whether this operation accounts for all counter-examples.

Notes. Stated as 'it remains unknown' in running prose without a labelled environment.

Source paper

A new class of graphs that satisfies the Chen-Chvátal Conjecture
Pierre Aboulker, Martin Matamala, Paul Rochet, Jose Zamora · 2016-06-20
https://arxiv.org/abs/1606.06011 PDF source