Metraipolis › archive › dc_bc54b120ec19

A Proof of the B-Free Graphs Conjecture — arXiv:2608.22537

Source
arXiv (en)
Original
https://arxiv.org/abs/2608.22537
License (as archived)
CC0-1.0
Archived
2026-10-18T08:32:57.674Z
SHA-256 of the archived text
5dccb744d2b6ec045f78c1dfe22c44e255a06e0ad56f7a80e9ee71e55ba5b12e
Stable URL of this page
https://metraipolis.com/documento/dc_bc54b120ec19

How to cite

A Proof of the B-Free Graphs Conjecture — arXiv:2608.22537 — arXiv (en), https://arxiv.org/abs/2608.22537 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_bc54b120ec19 (Metraipolis archive dc_bc54b120ec19, sha256 5dccb744d2b6ec045f78c1dfe22c44e255a06e0ad56f7a80e9ee71e55ba5b12e)
BibTeX
@misc{dcbc54b120ec19,
  title = {A Proof of the B-Free Graphs Conjecture — arXiv:2608.22537},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2608.22537},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_bc54b120ec19; sha256 5dccb744d2b6ec045f78c1dfe22c44e255a06e0ad56f7a80e9ee71e55ba5b12e},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2608.22537. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Let $\mathcal{B}$ be the class consisting of the six-vertex bipartite graphs that possess a perfect matching and their complements. It is proved that every $\mathcal{B}$-free graph $G$ satisfies $\alpha(G)+\omega(G)\ge |V(G)|-1$. This establishes Conjecture 3.1 of Litjens, Polak and Sivaraman (B-Free Graphs Conjecture). For a smallest counterexample, Hall-type exchange arguments show that two maximum stable sets, and likewise two maximum cliques, differ in at most two vertices. A core-corona matching lemma then forces $|\alpha(G)-\omega(G)|\le 2$. Double counting between suitably dense and sparse vertices reduces the problem to twenty-one binary feasibility systems on at most fourteen vertices. Their infeasibility is verified by two independent exact encodings, with a separate exhaustive validation of the forbidden-family constraints.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-08-25 in math.CO).
Categorie arXiv: Combinatorics (math.CO).
Pagina del lavoro: https://arxiv.org/abs/2608.22537 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-18T08:27:54.414Z dalla pagina https://arxiv.org/catchup/math.CO/2026-08-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).