Large independent sets in triangle-free cubic graphs: beyond planarity
Advances in Combinatronics (2020)
Voir la notice de l'article provenant de la source Advances in Combinatronics website
Every $n$-vertex planar triangle-free graph with maximum degree at most $3$
has an independent set of size at least $\frac{3}{8}n$. This was first
conjectured by Albertson, Bollob\'as and Tucker, and was later proved by
Heckman and Thomas. Fraughnaugh and Locke conjectured that the planarity
requirement could be relaxed into just forbidding a few specific nonplanar
subgraphs: They described a family $\mathcal{F}$ of six nonplanar graphs (each
of order at most $22$) and conjectured that every $n$-vertex triangle-free
graph with maximum degree at most $3$ having no subgraph isomorphic to a member
of $\mathcal{F}$ has an independent set of size at least $\frac{3}{8}n$. In
this paper, we prove this conjecture.
As a corollary, we obtain that every $2$-connected $n$-vertex triangle-free
graph with maximum degree at most $3$ has an independent set of size at least
$\frac{3}{8}n$, with the exception of the six graphs in $\mathcal{F}$. This
confirms a conjecture made independently by Bajnok and Brinkmann, and by
Fraughnaugh and Locke.
Publié le :
@article{ADVC_2020_a4,
author = {Wouter Cames van Batenburg and Jan Goedgebeur and Gwena\"el Joret},
title = {Large independent sets in triangle-free cubic graphs: beyond planarity},
journal = {Advances in Combinatronics},
publisher = {mathdoc},
year = {2020},
language = {en},
url = {http://geodesic.mathdoc.fr/item/ADVC_2020_a4/}
}
Wouter Cames van Batenburg; Jan Goedgebeur; Gwenaël Joret. Large independent sets in triangle-free cubic graphs: beyond planarity. Advances in Combinatronics (2020). http://geodesic.mathdoc.fr/item/ADVC_2020_a4/