\documentclass[20pt, landscape]{foils}
\usepackage{amssymb,amsthm,graphics,ams, amsmath}

\addtolength{\textwidth}{2cm}
\addtolength{\hoffset}{-1cm}
\addtolength{\textheight}{2cm}
\addtolength{\voffset}{-1cm}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{definition}{Definition}
\newtheorem{conjecture}{Conjecture}

%% \newcommand{\Z}{\mathbb Z}

\begin{document}
\title{Steiner Colorings of Cubic Graphs}
\date{April 22, 2004}
\author{D\'avid P\'al}
\maketitle

\begin{center}
Advisor: Martin \v Skoviera\\

\includegraphics{projective15}

Comenius University\\
Department of Computer Science

\end{center}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Ordinary Edge Colorings}

Let $G$ be a cubic graph. 
Using some set of colors we color its egdes.
The colors of the edges meeting at a vertex must be all distinct.

\bigskip

\begin{theorem}[Vizing, 1964]
Cubic graph can be colored by either $3$ or $4$ colors.
\end{theorem}

\begin{figure}
\begin{center}
\includegraphics{cubic}
\hspace{3cm}
\includegraphics{petersen}
\end{center}
\caption{Three-sided prism and the Petersen graph}
\end{figure}

Graphs that need 4 colors are called \emph{Snarks}.
Snarks include all graphs with bridges, Petersen graph and infinitely
many others.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Steiner Triple Systems and Steiner Colorings}

We allow more than three colors. However we allow only some triples of
colors of edges at a vertex. Moreover, at a vertex colors of two edges
should determine the color of the third.
\bigskip

\begin{definition}
\emph{Steiner triple system} $\mathcal S$ is a tuple $\mathcal S = (P,
T)$, where $P$ is set of finite set of points, and $T$ is system of triples of points such that each
pair of points is contained in exactly one triple of $T$.
\end{definition}

We color edges of a cubic graph by points of a Steiner system, in such way that the
colors of the three edges meeting at a vertex forms a triple of the
Steiner system.

The general question is: "Which Steiner systems color which cubic graphs?".

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Examples of Steiner Triple Systems}

\begin{itemize}
\item Trivial STS, $\mathcal T = (\{0,1,2\},\{\{0,1,2\}\})$.
\item Fano plane $\mathcal F = PG(2,2) = (\Z_2 \times \Z_2 \times \Z_2
- \{0,0,0\}, \{\{x,y,z\} \ |\ x+y+z = 0 \} )$

\end{itemize}

\begin{figure}
\begin{center}
\includegraphics{fano-plane}
\end{center}
\caption{Fano plane}
\end{figure}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Graphs without bridges}

Holroyd and \v Skoviera showed that:
\bigskip

\begin{theorem}
Every bridgeless cubic graph can be colored by any non-trivial Steiner
system.
\end{theorem}

\bigskip

\begin{theorem}
Every simple cubic graph can be colored by a particular Steiner system
of order $381$.
\end{theorem}

Our motivation was to study graph with bridges and to lower the $381$ bound.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Weak colorings}

If $\mathcal S_1, \mathcal S_2, \dots, \mathcal S_n$
are Steiner systems. Then also
$\mathcal S_1 \times \mathcal S_2 \times \dots \times \mathcal S_n$
is a Steiner system.
The set of points is $P(\mathcal S_1) \times P(\mathcal S_2) \times
\dots \times P(\mathcal S_n).$
Triples are of the form
$$
\{(a_1,a_2, \dots, a_n), (b_1,b_2, \dots, b_n), (c_1,c_2, \dots, c_n)\}, 
$$
such that $\{a_i, b_i, c_i\}$ is a triple of $\mathcal S_i$ or
$a_i=b_i=c_i$, for all $i=1,2,\dots,n$.
And for at least one $i$ holds the former case.

Coloring by the system $\mathcal S_1 \times \mathcal S_2 \times \dots
\times \mathcal S_n$ can be understood as a collection of colorings by
the individual Steiner systems $\mathcal S_i$.  However in such
$\mathcal S_i$-coloring, we can allow also vertices at which edges of
three identical colors meet.  We call such colorings \emph{weak}, and
such vertices \emph{singular}.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Affine colorings}

The Steiner system $AG(n,3) = \mathcal T \times \mathcal T
\dots \times \mathcal T$ is called \emph{affine}.

\begin{figure}
\begin{center}
\includegraphics{aff9}
\caption{Affine plane $AG(2,3) = (\Z_3 \times \Z_3, \{\{x,y,z\}\ |\ x+y+z=0\})$}
\end{center}
\end{figure}


\newpage

\begin{figure}
\begin{center}
\includegraphics{bridge}
\end{center}
\caption{A graph with a bridge colored by the affine plane AG(2,3)}
\end{figure}

To find an affine coloring it suffices to find a suitable set of
weak $3$-edge-colorings with disjoint sets of singular vertices.

Notice that in any weak affine coloring at each vertex the
colors of incident edges sum to zero.
\newpage

By a 'flow-like' argument it can be shown, that cubic graph with a bridge with a
\emph{bipartite end} can not be affinely colored. The bridge end is
always singular in any weak $3$-edge-coloring.

\begin{figure}
\begin{center}
\includegraphics{k33}
\end{center}
\caption{$K_{3,3}$ with a subdived edge and bridge attached.}
\end{figure}

\begin{equation*}
\begin{split}
0 &= \sum_{\rm all\ edges\ except\ the\ bridge} \phi(e) - \phi(e) \\
&= \phi(vy) - \phi(vx) + 
\mspace{-18.0mu} \sum_{{\rm edges\ incident\ with\ } X} \mspace{-30.0mu} \phi(e) -  
\mspace{-18.0mu} \sum_{{\rm edges\ incident\ with\ } Y} \mspace{-30.0mu} \phi(e)  
= \phi(vy) - \phi(vx) 
\end{split}
\end{equation*}

\newpage

\begin{lemma}
Every simple cubic graph is weak $\mathcal S$-colorable
such that only the bridge ends are singular, for every
non-trivial transitive Steiner system $\mathcal S$.
\end{lemma}

\bigskip

\begin{lemma}
\label{l}
Every cubic graph without a bridge with a bipartite end is weakly 
$3$-edge-colorable, such that bridge ends are regular.
\end{lemma}

\bigskip

\begin{theorem}
Every cubic graph without a bridge with a bipartite end is
$AG(n,3)$-colorable, for $n \ge 3$.
\end{theorem}

The idea of the proof is to employ the theorem of Holroyd and \v Skoviera on
$2$-edge-connected components of a graph, and resolve the bridges.

The problem of affine colorings is thus almost solved. The only
open problem remains: "Which graphs is $AG(2,3)$-colorable?" We conjecture that
$AG(2,3)$ colors exactly the same class of graphs as $AG(n,3), n\ge 3$.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Projective colorings}

The $n$-dimensional \emph{projective} Steiner system $PG(n,2)$ has
point set 
$$\underbrace{\Z_2 \times \Z_2 \times \dots \times \Z_2}_{n+1 \rm\ times} - \{(0,0,\dots,0)\}$$
and triples 
$$\{x,y,z\}, \quad x+y+z=(0,0,\dots,0).$$
Since $-1=1$ in $\Z_2$, projective colorings are just group-valued nowhere-zero flows.
We can employ all known results about flows (Tutte, Seymour):
\begin{itemize}
\item Graphs with bridges have no nowhere-zero flow.
\item Only the order of the group matters. (The larger the group the better.)
\item Every bridgeless graph has a $6$-flow.
\end{itemize}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Colorings by Fano plane}

The Fano plane is $2$-dimensional projective Steiner system, $\mathcal
F = PG(2,2)$. $\mathcal F$-coloring is a $8$-flow, thus $\mathcal F$-colorable
are exactly the bridgless graphs.

However, the novel idea is to study weak Fano colorings:
\bigskip

\begin{lemma} 
Bipartite cubic graph with a subidivided edge and bridge
attached is weakly $\mathcal F$-colorable, in such way that the bridge end is
regular.
\end{lemma}

Combining with the Lemma \ref{l}, we improve the result of Holroyd and \v
Skoviera.

\bigskip

\begin{lemma}
Every simple cubic graph is $\mathcal T \times \mathcal F$-colorable.
\end{lemma}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Open problems}

\begin{conjecture}
All graphs without bipartite end are $AG(2,3)$-colorable.
\end{conjecture}

\bigskip

\begin{conjecture}
Any non-projective, non-affine Steiner system colors every simple
cubic graph.
\end{conjecture}

In particular, we conjecture that any of the two Steiner systems of
order $13$ colors every cubic simple graph.

There is also strong connection of Steiner colorings to perfect matchings.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\foilhead{Connection with Perfect Matchings}

\begin{theorem}[Petersen, 1891]
Every bridgeless cubic graph has a perfect matching.
\end{theorem}

\begin{figure}
\begin{center}
\includegraphics{matching}
\caption{Perfect matching in the Petersen graph}
\end{center}
\end{figure}

\newpage

\begin{conjecture}[Fan-Raspaud, 1994]
Every bridgeless cubic graph contains three perfect matchings with empty intersection.
\end{conjecture}

\bigskip

\begin{conjecture}[Berge-Fulkerson]
Every bridgeless cubic graph contains six perfect matchings such that
each edge appears in exactly two of them.
\end{conjecture}

Both of these conjectures can be formulated in terms of Steiner colorings
in which we are allowed to use only some subset of the triples.

\end{document}

