Independence number of 2-factor-plus-triangles graphs (Q1010933)

Summary: A 2-factor-plus-triangles graph is the union of two 2-regular graphs \(G_1\) and \(G_2\) with the same vertices, such that \(G_2\) consists of disjoint triangles. Let \({\mathcal G}\) be the family of such graphs. These include the famous ``cycle-plus-triangles'' graphs shown to be 3-choosable by Fleischner and Stiebitz. The independence ratio of a graph in \({\mathcal G}\) may be less than \(1/3\); but achieving the minimum value \(1/4\) requires each component to be isomorphic to the 12-vertex ``Du--Ngo'' graph. Nevertheless, \({\mathcal G}\) contains infinitely many connected graphs with independence ratio less than \(4/15\). For each odd \(g\) there are infinitely many connected graphs in \({\mathcal G}\) such that \(G_1\) has girth \(g\) and the independence ratio of \(G\) is less than \(1/3\). Also, when \(12\) divides \(n\) (and \(n\neq 12\)) there is an \(n\)-vertex graph in \({\mathcal G}\) such that \(G_1\) has girth \(n/2\) and \(G\) is not 3-colorable. Finally, unions of two graphs whose components have at most \(s\) vertices are \(s\)-choosable.