×

Large independent sets in triangle-free cubic graphs: beyond planarity. (English) Zbl 1450.05064

Summary: Every \(n\)-vertex planar triangle-free graph with maximum degree at most 3 has an independent set of size at least \(\frac38 n\). This was first conjectured by M. Albertson et al. [in: Proc. 7th Southeast. Conf. Comb., Graph Theory, Comput.; Baton Rouge 43–50 (1976; Zbl 0344.05156)], and was later proved by C. C. Heckman and R. Thomas [Discrete Math. 233, No. 1–3, 233–237 (2001; Zbl 0982.05071)]. K. Fraughnaugh and S. C. Locke [J. Comb. Theory, Ser. B 65, No. 1, 51–72 (1995; Zbl 0828.05032)] 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 \(\frac38 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 \(\frac38 n\), with the exception of the six graphs in \(\mathcal{F}\). This confirms a conjecture made independently by B. Bajnok and G. Brinkmann [J. Comb. Math. Comb. Comput. 26, 237–254 (1998; Zbl 0898.05036)], and by Fraughnaugh and Locke [loc. cit.].

MSC:

05C69 Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.)
05C35 Extremal problems in graph theory
05C10 Planar graphs; geometric and topological aspects of graph theory
PDFBibTeX XMLCite
Full Text: DOI arXiv