\magnification=1200
\hsize=4in
\overfullrule=0pt
\input amssym
%\def\frac#1 #2 {{#1\over #2}}
\def\emph#1{{\it #1}}
\def\em{\it}
\nopagenumbers
\noindent
%
%
{\bf Jennifer Vandenbussche and Douglas B. West}
%
%
\medskip
\noindent
%
%
{\bf Independence Number of 2-Factor-Plus-Triangles Graphs}
%
%
\vskip 5mm
\noindent
%
%
%
%
A {\it 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.

\bye

.