Independence number of 2-factor-plus-triangles graphs

Jennifer Vandenbussche ; Douglas B. West

The electronic journal of combinatorics, Tome 16 (2009) no. 1

Résumé

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 ${\cal 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 ${\cal 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, ${\cal G}$ contains infinitely many connected graphs with independence ratio less than $4/15$. For each odd $g$ there are infinitely many connected graphs in ${\cal 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\ne12$) there is an $n$-vertex graph in ${\cal 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.

Détail

DOI : 10.37236/116

Classification : 05C69