Independence number of 2-factor-plus-triangles graphs
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.
- An algorithm for identifying cycle-plus-triangles graphs
- On the tightness of the \(\frac {5}{14}\) independence ratio
- scientific article; zbMATH DE number 1151823
- Triangle-free planar graphs with the smallest independence number
- 11/30 (Finding large independent sets in connected triangle-free 3- regular graphs)
This page was built for publication: Independence number of 2-factor-plus-triangles graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1010933)
