Finite exceptions to ℓ(G)+br(G)≥|G|
Conjecture 2.2 · arXiv:1606.06011
Status open medium confidence
Conjecture 2.2 from arXiv:1606.06011 proposes that all counterexamples to ℓ(G) + br(G) ≥ |G| among graphs without a pendant edge form a finite exceptional family F_0; the source paper identified three minimal counterexamples with a bridge. Searches of the subsequent Chen-Chvátal literature (including papers on bisplit graphs, diameter-3 graphs, and improved metric-space lower bounds) found no paper that resolves or substantially advances this specific finite-family conjecture. The conjecture appears to remain open as of 2026, though the 10-year gap and limited indexed coverage leave medium confidence.
Reviewer notes. No follow-up paper addressing Conjecture 2.2 specifically (the finite exceptional family F_0 for graphs without pendant edges) was found. Related Chen-Chvátal papers found (2310.15058 on metric-space lower bounds; 2512.12047 on diameter-3 graphs; 1808.08710 on bisplit graphs) do not discuss the pendant-edge/bridge finite-family conjecture. Confidence is medium rather than high because the conjecture is ~10 years old and resolution in a venue not indexed by our searches cannot be ruled out.
Context
The authors observe that replacing a bridge by a path of arbitrary length in a counter-example to $\ell(G)+\mathrm{br}(G)\geq|G|$ yields infinitely many counter-examples, so finitely many minimal ones cannot account for all exceptions; they propose that graphs with a pendant edge should be excluded and that all remaining counter-examples come from a finite family. The three known minimal counter-examples with a bridge are depicted in Figure 2.
Also stated in
Notes. Source is PDF; statement is cleanly readable.
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