Independence number of 2-factor-plus-triangles graphs
type: Item
instance of: scholarly article
title: Independence number of 2-factor-plus-triangles graphs
zbMATH Open document ID: 1178.05070
author: Jennifer Vandenbussche
author: Douglas B. West
published in: The Electronic Journal of Combinatorics
publication date: 2009-04-07T00:00:00Z
full work available at URL: https://eudml.org/doc/117306
full work available at URL: v16i1r27.html
review text: 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.
Mathematics Subject Classification ID: 05C69
zbMATH DE Number: 5541092
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 5541092