go-v.orgdoi

Independence Number of 2-Factor-Plus-Triangles Graphs

Jennifer Vandenbussche, Douglas B. West · The Electronic Journal of Combinatorics · 2009

  • DOI 10.37236/116
  • Publisher Electronic Journal of Combinatorics
  • Type article
  • Issued 2009

Not cached yet. This record was fetched live for this request and is stored after the lookup. Reopening the page should serve the cached copy.

The Electronic Journal of Combinatorics · Electronic Journal of Combinatorics · article · 2009

Abstract

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.

Open the resolved locator · 10.37236/116

Metadata licence: OpenAlex metadata (CC0)