Cames van Batenburg, Wouter; Goedgebeur, Jan; Joret, Gwenaël Large independent sets in triangle-free cubic graphs: beyond planarity. (English) Zbl 1450.05064 Adv. Comb. 2020, Paper No. 7, 45 p. (2020). 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.]. Cited in 3 Documents 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 Keywords:planar triangle-free graph Citations:Zbl 0344.05156; Zbl 0982.05071; Zbl 0828.05032; Zbl 0898.05036 PDFBibTeX XMLCite \textit{W. Cames van Batenburg} et al., Adv. Comb. 2020, Paper No. 7, 45 p. (2020; Zbl 1450.05064) Full Text: DOI arXiv