\documentclass[12pt,a4paper,titlepage]{article}

\usepackage{amsthm}
\usepackage{amsmath}
%\usepackage{graphics}
\usepackage{epsfig}
\usepackage{amssymb}
%\pagestyle{empty}


\newtheorem{definition}{Definition}
\newtheorem{proposition}[definition]{Proposition}
\newtheorem{lemma}[definition]{Lemma}
\newtheorem{theorem}[definition]{Theorem}
\newtheorem{conjecture}[definition]{Conjecture}

\newcommand{\p}{\mid} %% | separator used in {x | V(x)}

\newcommand{\Z}{\mathbb{Z}}
\newcommand{\mc}{\mathcal }
\newcommand{\TODO}{{\bf TODO}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% add meta info if creating PDF
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\newif\ifpdf
%\ifx\pdfoutput\undefined
%  \pdffalse
%\else
%  \pdfoutput=1 \pdftrue
%\fi

%\ifpdf
%  \pdfinfo{
%    /Title (Steiner Colorings of Cubic Graphs)
%    /Author (David Pal)
%    /Creator (PDFLaTeX)
%  }
%\else
%\fi


\begin{document}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% TITLE PAGE %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\title{Steiner Colorings of Cubic Graphs}
\author{D\'avid P\'al}
\date{April 2004}

\begin{titlepage}
\begin{center}
{\Huge Steiner Colorings of Cubic Graphs}\\
\bigskip
\bigskip
\includegraphics[width=0.5\textwidth]{komlogo}\\
\vfil
\textsc{
Diploma Thesis\\
Presented to the Academic Faculty of\\
Department of Computer Science\\
Faculty of Mathematics, Physics and Informatics\\
Comenius University\\
In Partial Fulfillment for the Degree Magister\\
\bigskip
Advisor:} RNDr. Martin \v Skoviera, PhD.
\end{center}
\vfil
{\large Bratislava, April 2004\hfill D\'avid P\'al}\\
\end{titlepage}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%  INTRODUCTION %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Introduction}

Vizing's theorem tells us that cubic graphs are edge-colorable by
either $3$ or $4$ colors. Graphs for which $4$ colors are needed are
called \emph{Snarks}. (Btw. it is an NP-complete problem to determine
if given cubic graph is $3$-edge-colorable.) A coloring by $4$ colors is
easy to establish.
Therefore it was proposed by Archdeacon to study colorings such that some
prescribed set of triples of colors of the edges at a vertex are
allowed.  A very natural structure of triples is a Steiner triple
system.
 

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%% STEINER TRIPLE SYSTEMS AND COLORINGS %%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Steiner triple systems and colorings}

\begin{definition}
\emph{Steiner triple system} $\mc S$ is a pair $\mc S=(P, T)$, where
$P$ is finite set of points containing at least three elements and $T$
is family of $3$-element-subsets of $P$ (called triples) 
such that each $2$-element-subset of $P$ is contained in exactly one triple.
\end{definition}

The number of points of a Steiner triple system is called its
\emph{order}.  Instead of writing the longish 'Steiner
triple system' we shall write only \emph{Steiner system} or even only
\emph{system}. We hope there should arise no confusion from this.
The following easy proposition holds.

\begin{proposition}
Let $\mc S$ be a Steiner triple system of order $n$.
Then $$n \equiv 1 {\rm\ or\ } 3 \pmod 6.$$
\end{proposition}
\begin{proof}
Choose an arbitrary fixed point $v$. There are $n-1$ pairs of the form
$\{u,v\}, u\neq v$. Any triple containing $v$ covers two of these pairs. Therefore $n$ is odd.
Further, each triple covers exactly three pairs of points.
There are exactly $\binom{n}{2} = n(n-1)/2$ pairs of points to be covered.
While each pair is covered exactly once by the triples, we have $3|n(n-1)/2$. 
The only odd solutions modulo $6$ are $1$ and $3$.
\end{proof}

The converse is also true. That is, if $n \ge 3$ and $n \bmod 6$ is
either $1$ or $3$, then there exists a (cyclic) Steiner triple system of order $n$.  
Hence, there exist systems of orders
$3,7,9,13,15,19,21,\dots$ and systems of other orders do not.

\begin{figure}
\begin{center}
\includegraphics{fano-plane}
\caption{The Fano plane. Straight lines and the circle form the triples.}
\label{fig:fano-plane}
\end{center}
\end{figure}
The simplest Steiner system is the \emph{trivial} Steiner system 
of order $3$ consisting of only one triple.  We will denote it by the
letter $\mc T$.
The smallest nontrivial
Steiner triple system is the so called \emph{Fano plane} depicted on
Figure \ref{fig:fano-plane}. It is the only system of order 7. 
As its point set we take nonzero vectors over the field $\Z_2$ of
length three
$\Z_2 \times \Z_2 \times \Z_2 - \{(0,0,0)\}$. 
As the set of triples we take all triples $\{a,b,c\}$ where $a+b+c = (0,0,0)$. 
We will denote the Fano plane by $\mc F$.

To create larger Steiner systems two generic constructions can be
used.

\begin{theorem}[$2n+1$-construction]
For each  Steiner triple system of order $n$
there exists a Steiner triple system of order $2n+1$.
\end{theorem}

\begin{proof}
Let $\mc S=(P,T)$ be any Steiner system of order $n$.
Let us take an isomorphic copy of the system $\mc S$, which we will
denote $\mc S'=(P', T')$ together with the isomorphism $v \mapsto v'$ for every
point $v \in P$.
Further let $x$ be a new
$(2n+1)$-th point. Then $\mc S''=(P'', T'')$, $P''=P \cup P' \cup \{x\}$ and
$$T'' = T \cup
\{ \{u,v',w'\} \p \{u,v,w\} \in T \} \ \cup
\{ \{v,v',x\} \p v \in P \}$$
is Steiner triple system of order $2n+1$.
\end{proof}

Starting with the trivial Steiner triple system and successively using
$2n+1$-construction we form the class of the so called
\emph{projective} Steiner systems. They can be easily algebraically
described as the projective spaces over the field $\Z_2$.  
After $n-1$ contructions we get a system isomorphic to the $n$ dimensional
projective space over the field $\Z_2$ denoted by $PG(n,2)$.
It has order $2^{n+1}-1$ and the point set
is $$\underbrace{\Z_2 \times \Z_2 \times \dots \times \Z_2}_{n+1\rm{\
times}} - \{(0,0,\dots,0)\}.$$ The set of triples is formed by all
the triples $\{a,b,c\}$ where $a+b+c = (0,0,\dots,0)$.   For example, 
the trivial Steiner system is a one-dimensional projective space
and the Fano plane is a two-dimensional projective space, i.e. a projective plane.

\begin{theorem}[Direct product]
Let $\mc S=(P_{\mc S},T_{\mc S})$ and $\mc R=(P_{\mc R},T_{\mc R})$ be two Steiner triple
systems of order $m$ and $n$ respectively. Then there exists a Steiner
triple system of order $mn$.
\end{theorem}

\begin{proof}
As the point set of the system we take $P_{\mc S} \times P_{\mc R}$. The triples
are formed as follows
\begin{equation*}
\begin{split}
& \{\{(s_1,r), (s_2,r), (s_3,r)\} \p \{s_1,s_2,s_3\} \in T_{\mc S}, r\in P_{\mc R} \}\ \cup \\
&\{\{(s,r_1), (s,r_2), (s,r_3)\} \p s \in P_{\mc S}, \{r_1,r_2,r_3\} \in T_{\mc R}\}\ \cup \\
&\{\{(s_1,r_1), (s_2,r_2), (s_3,r_3)\} \p \{s_1,s_2,s_3\} \in T_{\mc S}, \{r_1,r_2,r_3\} \in T_{\mc R} \}.
\end{split}
\end{equation*}
\end{proof}

We will denote $\mc S \times \mc R$ the resulting Steiner triple
system from the preceding theorem. Of course, this construction can be
easily generalized to more than two systems $\mc S_1, \mc S_2, \dots,
\mc S_k$ forming more complex system $\mc S_1 \times \mc S_2 \times
\dots \times \mc S_k$.

As with the $2n+1$-construction, direct product of trivial Steiner
systems gives us the family of the \emph{affine} Steiner systems.
Again, these can be easily algebraically described as the affine
spaces over the field $\Z_3$.  The Steiner system $$\underbrace{\mc T
\times \mc T \times \dots \times \mc T}_{n{\rm-times}}$$ is isomorphic
to the affine space $AG(n,3)$.  Its points set is $$\underbrace{\Z_3
\times \Z_3 \times \dots \times \Z_3}_{n{\rm-times}}$$ and the triples
are of the form $\{a,b,c\}$, $a+b+c=0$, $a\neq b$, $b\neq c$, $a \neq
c$.  

In both the projective and affine Steiner systems the triples are
actually the geometrical lines of the underlying spaces.
From this reason the abbreviations $AG$ and $PG$---meaning affine and
projective \emph{geometry}---are used in both geometrical and
combinatorial design literature.

\begin{figure}
\begin{center}
\includegraphics{aff9}
\end{center}
\caption{Affine plane $AG(2,3)$. Straight lines and curves form the triples.}
\end{figure}
 

\begin{definition}
Let $G=(V,E)$ be cubic graph and $\mc S = (P, T)$ a Steiner
triple system. A \emph{Steiner coloring} is a map $\phi : E \to P$, such
that the colors $\phi(e_1), \phi(e_2), \phi(e_3)$ of the three edges
$e_1, e_2, e_3$ meeting at any vertex form a triple of $\mc S$.
\end{definition}

\begin{definition}
Let $G=(V,E)$ be cubic graph and $\mc S = (P,T)$  a Steiner
triple system. A \emph{weak Steiner coloring} is
a map $\phi : E \to P$, such that the colors $\phi(e_1), \phi(e_2),
\phi(e_3)$ of the three edges $e_1,e_2,e_3$ meeting at any vertex
either form a triple of $\mc S$ or
$\phi(e_1)=\phi(e_2)=\phi(e_3)$.
\end{definition}

A (weak) coloring by a Steiner triple system $\mc S$ will be called a
(weak) $\mc S$-coloring, for short.
There is no difference between a $3$-edge-coloring and a $\mc
T$-coloring, and we will use these two terms interchangeably.

A weak Steiner coloring divides the set of vertices of a graph into
two categories: The set of vertices at which the colors of
the three incident edges form a triple of the Steiner system, and the
set of vertices at which all the three incident edges have the same
color. We will call the former vertices \emph{regular} and the latter
vertices \emph{singular}. (Holroyd and \v Skoviera \cite{skoviera2}
used the term 'weak'.)

Two weak colorings of a graph by two Steiner triple systems can be
combined to form a weak coloring by their direct product, as the
following theorem shows.

\begin{theorem}
\label{theorem:mn}
Let $G$ be a cubic graph, let $\mc S, \mc R$ be two Steiner
triple systems, and finally let $\phi$ be a weak $\mc S$-coloring and $\psi$ be
a weak $\mc R$-coloring of $G$.
Then there exists a $\mc S \times \mc R$-coloring such the set
of singular vertices is the intersection of the sets of singular vertices
of $\phi$ and $\psi$.
\end{theorem}

\begin{proof}
Let us construct the coloring $\chi$ of the graph $G$ by the system $\mc
S \times \mc R$ as the cartesian product of the colorings $\phi$ and
$\psi$, that is $$\chi(e) = (\phi(e), \psi(e)), \qquad e \in E(G).$$ Look at three edges
$e_1, e_2, e_3$ meeting at any vertex $v \in G$.  If $v$ is regular in
one or both of the colorings $\phi, \psi$ i.e.  $\phi(e_1), \phi(e_2),
\phi(e_3)$ is triple of $\mc S$ or $\psi(e_1), \psi(e_2), \psi(e_3)$
is triple of $\mc R$ or both are, then $\chi(e_1)=(\phi(e_1),
\psi(e_1))$, $\chi(e_2)=(\phi(e_2), \psi(e_2))$,
$\chi(e_3)=(\phi(e_3), \psi(e_3))$ is triple of $\mc S \times \mc R$
and $v$ is regular in the coloring $\chi$.

If $v$ is singular in both $\phi$ and $\psi$, that is $\phi(e_1) =
\phi(e_2) = \phi(e_3)$ and $\psi(e_1) = \psi(e_2) = \psi(e_3)$, then
$\chi(e_1)=(\phi(e_1), \psi(e_1)) = \chi(e_2)=(\phi(e_2), \psi(e_2)) =
\chi(e_3)=(\phi(e_3), \psi(e_3))$ and $v$ is singular in $\chi$.

In any case, $\chi$ is a correct weak Steiner coloring.
\end{proof}

Most important will be the case when the sets of singular vertices of the two
colorings are disjoint. Then the resulting coloring will be a (non-weak)
Steiner coloring.


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% BASICS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Basics}

In this chapter we prove some facts about Steiner colorings of cubic
graphs.  We allow graphs to have parallel edges and self-loops.
However, note that a graph with a self-loop is not colorable by
any Steiner system.   Parallel edges can be easily avoided by using the
following two reductions

\begin{proposition}[Reduction of a triple edge]
Let $\mc S$ be a Steiner system. Let $G$ be cubic graph with a triple edge
between vertices $x$ and $y$. Then $G'=G-\{x,y\}$ is $\mc S$-colorable if
and only if $G$ is.
\end{proposition}

\begin{proof}
Clearly, any $\mc S$-coloring of $G$ is also a $\mc S$-coloring of $G'$. Conversely, any $\mc S$-coloring
of $G'$ can be extended to a coloring of $G'$ -- it suffices to color
the triple edge $xy$ by any triple of $\mc S$.
\end{proof}


\begin{figure}
\begin{center}
\label{figure:double-edge}
\includegraphics{double-edge}
\caption{Reduction of a double edge.}
\end{center}
\end{figure}

\begin{proposition}[Reduction of a double edge]
Let $\mc S$ be a Steiner system. Let $G$ be cubic
graph with a double edge between the vertices $x$ and $y$. Let $G'$ be cubic
graph  obtained from $G$ by contracting $x,y$ and suppressing the
$2$-valent vertex. Then $G'$ is $\mc S$-colorable if and only if $G$ is.
\end{proposition}

\begin{proof} Let be $u,v$ be neighbouring vertices of the double edge
$xy$; $ux, yv \in E(G)$. (See Figure \ref{figure:double-edge}.)  Let us
have any $\mc S$-coloring of $G'$ and let $c_1$ be the color of edge
$uv$ of $G'$.  This coloring can be extended to a coloring of $G$:
Color the double edge $xy$ by any colors $c_2, c_3$ such that ${c_1,
c_2, c_3}$ form a triple of $\mc S$ and assign the color $c_1$ to both
the edges $ux$ and $yv$.

Conversely, let us have a $\mc S$-coloring of $G$. Necessarily the
edges $ux$ and $vy$ have the same color $c$. Therefore after reduction
of the double edge we can assign to the edge $uv$ the color $c$ and
leave the colors of the other edges untouched.
\end{proof}

If a cubic graph $G$ has parallel edges, we can always reduce it to a
graph $G'$ without parallel edges by a series of these two reductions.
$G'$ is colorable by some Steiner system $\mc S$ if and only if $G$ is.  
However a self-loop may appear in $G'$ and therefore nor
$G'$ nor $G$ is not colorable by any Steiner system.  
To explain when self-loops appears, we must define the class of
series-parallel graphs.

\begin{definition}
A \emph{series-parallel} graph is recursively defined as follows:
\begin{itemize}
\item The disjoint union of any number of the graphs $K_1$ and $K_2$ is series-parallel.
\item A graph obtained from a series-parallel graph by subdivision of an edge is series-parallel.
\item A graph obtained from a series-parallel graph by creating a
parallel edge is series-parallel.
\end{itemize}
\end{definition}

It is clear that if cubic graph can be reduced to an empty graph by
reducing double and triple edges, it must be series-parallel.  It also
easy to see that this can be taken as a characterization of a cubic
series-parallel graph.  Since both the reductions of double and triple
edges preserve bipartiteness and bridgelessness, cubic series-parallel
graphs are both bridgeless and bipartite.

\begin{definition}
Let $G$ be a cubic graph. An end vertex $v$ of a bridge 
is called a \emph{series-parallel end}, if after removing the bridge and supressing $v$ the component 
containing $v$ becomes series-parallel.
\end{definition}

The block with a series-parallel end can not contain any other cut
vertex other than $v$, because cubic series-parallel graphs are
bridgeless.  In other words, a series-parallel end lies in a leaf of
the block graph. 

The block with a series-parallel end reduces to a self-loop and
hence the series-parallel ends are an obstruction to Steiner colorings
at all. All other cubic graphs can be colored by at a least one
Steiner system \cite{skoviera1}.  In particular, bridgeless cubic
graphs can not have a series-parallel end and are thus Steiner
colorable.

The following fundamental theorem can be found in \cite{skoviera2}.

\begin{theorem}
\label{theorem:general-bridgeless}
Every bridgeless cubic graph admits $\mc S$-coloring, for any non-trivial
Steiner system $\mc S$.
\end{theorem}

Recall that if for any two points $x,y$ of a Steiner system there
exists an automorphism mapping $x$ to $y$, then the
system is called point-transitive. We can deduce easily the following.

\begin{theorem}
\label{theorem:general-bridges}
Let $\mc S$ be any non-trivial point-transitive Steiner system.
Every cubic graph has a weak $\mc S$-coloring where the singular vertices
are exactly the end-vertices of bridges.
\end{theorem}

\begin{proof}
After removing bridges from the graph  2-connected components and
isolated vertices remain.  Let $G_1, G_2, \dots, G_k$ be ordering of
both isolated vertices and 2-connected components such, that $G_i$ connects to $G[G_1, G_2,
\dots, G_{i-1}]$ by at most one bridge $b_i$.  
(This can be always done, while the the block graph is always a forest.)
Denote $G_i''$ the graph $G_i$ with all adjacent bridges attached.
Denote $G_i'$ the graph obtained from $G_i$ suppressing the $2$-valent
vertices. 

The graph $G_i'$ does not contain bridges and hence has a $\mc
S$-coloring. Reinsert the $2$-valent vertices and attach all the
adjacent bridges. The three newly created edges at some bridge end
will posses the color of the subdivided edge. We have thus obtained 
weak  $\mc S$-coloring of $G_i''$ in which only the bridge ends are
singular. Moreover since $\mc S$ is point-transitive, the coloring can
be choosen with any prescribed color of $b_i$.

\begin{figure}
\begin{center}
\includegraphics{weak-fano}
\caption{Connecting $G_i' = G_6$ to preceding components.}
\end{center}
\end{figure}

We will succesively color $G_1'' \cup G_2'' \cup  \dots \cup G_i''$, for
$i=1,2,\dots,k$. Clearly $G_1''$ can be colored. The rest of the
sequence can be accomplished by succesively adding $G_i''$ to
$G_1'' \cup G_2'' \cup  \dots \cup G_{i-1}''$. Since $G_i''$ and
and $G_1'' \cup G_2'' \cup \dots \cup G_{i-1}''$ have only $b_i$ or
even nothing in common, and the color of $b_i$ can be choosen, the coloring of
$G_1'' \cup G_2'' \cup  \dots \cup G_i'' \cup G_{i+1}''$ is easily
established.
\end{proof}

This theorem can be improved a little: The vertices, at which three
bridges meet, can be made regular in the coloring too.

Note that both the projective and the affine Steiner systems (including the
trivial system and the Fano plane) are point-transitive.  The 
authomorphisms are affine transformations or collineations,
respectively.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% AFFINE COLORINGS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Affine colorings}

\begin{definition}
Let $G$ be a cubic graph. And end vertex $v$ of a bridge is called a
\emph{bipartite end}, if
after removing the bridge and supressing $v$ the component containing 
$v$ becomes bipartite.
\end{definition}

Realize that after removing the bridge its bipartite end must lie in a block.  (That
is, the bipartite end must lie in a leaf of the block graph of $G$.)
This is caused by the nonexistence of a cubic bipartite graph with
bridges. Also note that series-parallel ends are just a special case
of bipartie ends and thus a cubic graph with no bipartite end necessarily
has no series-parallel end.
 
\begin{proposition} In a cubic graph each bipartite end is a
singular vertex of any weak affine coloring.  
\end{proposition}

\begin{proof}
Let $G$ be cubic graph with the bipartite end $v$.  For the
purpose of contradiction suppose that $\phi: E(G) \to \Z_3 \times \Z_3
\times \dots \times \Z_3$ is a weak 
coloring of $G$ by an affine Steiner triple system.
%(The dimension of the system is unimportant.)

Let $H$ be the block that contains the bipartite end $v$ and
let $x$ and $y$ be the neighbours of $v$ lying in $H$.
We suppress the vertex $v$ of degree two and call $H'$ the resulting
bipartite graph with partite sets $X,Y$, $x \in X$, $y \in Y$.  
The colors of the three edges $e_1, e_2, e_3$ at any vertex of $H$
satisfy $\phi(e_1) + \phi(e_2) + \phi(e_3) = (0,0,\dots,0)$, even in
case of singular vertex. Using this fact, a little algebra
\begin{equation*}
\begin{split}
(0,0,\dots,0) &= \sum_{e \in E(H)} (\phi(e) - \phi(e)) \\
&= \phi(vy) - \phi(vx) + \sum_{\substack{x' \in X \\ z \in V(H-X)}} \phi(x'z)  
 - \sum_{\substack{y' \in Y \\ z \in V(H-Y)}} \phi(y'z)  \\
&= \phi(vy) - \phi(vx) 
\end{split}
\end{equation*} shows that $\phi(vx) = \phi(vy)$ and hence $v$ is
singular.
\end{proof}

Hence the bipartite end is an obstruction to affine coloring,
in fact the only one. 
All other bridge ends can be made regular, it even suffices to use only trivial Steiner
system.
%We first prove a lemma, which will be needed in proof of the main theorem.

\begin{figure}
\begin{center}
\includegraphics{even-cycle}
\caption{Even cycle through non-bipartite end is either
$\pi_1\rho_1 \pi_2$ or $\pi_1\rho_2 \pi_2$.}
\label{fig:even-cycle}
\end{center}
\end{figure}


\begin{proposition} \label{proposition:evencycle}
Let $G$ be cubic graph and let $H$ be block of $G$ with a single
cut-vertex $v$. 
\begin{enumerate}
\item The vertex $v$ is bipartite end. %% (1)
\item Every cycle through $v$ in $H$ is odd. %% (2)
\end{enumerate}
\end{proposition}

\begin{proof}
The implication $1 \Rightarrow 2$ clearly holds. For $2 \Rightarrow 1$
to prove, it suffices to show that every cycle in $H$ not through $v$
is even. For the purpose of contradiction suppose there is an odd
cycle $C$ in $H$ not through $v$.
Since $H$ is 2-connected (and $G$ is cubic)
there exist two disjoint paths $\pi_1, \pi_2$ from $v$ to some two
distinct vertices $x$ and $y$ of $C$. Divide the cycle $C$ into two paths
$\rho_1, \rho_2$ between $x$ and $y$. (See Figure
\ref{fig:even-cycle}.) Then both $\pi_1 \rho_1
\pi_2$ and $\pi_1 \rho_2 \pi_2$ are cycles through $v$ and have
different parity. Therefore there is an even cycle through $v$
contradicting $2$.
\end{proof}
Clearly, if $v$ is not a bipartite end, then in $H$ there exists an
even cycle cycle through $v$.

\begin{lemma}
\label{lemma:affine-bridges}
Let $G$ be cubic graph which contains no bridge with bipartite end. 
There exists a weak $3$-edge-coloring, in which end vertices of the bridges 
are regular.
\end{lemma}

\begin{proof}
Decompose the graph into $2$-connected components and isolated
vertices. Let $G_1, G_2, \dots, G_k$ be all the $2$-connected components
or isolated vertices ordered in such way,
that $G_i$ is attached to $G[G_1, G_2, \dots, G_{i-1}]$ by at most one 
bridge $b_i$.  Attach all adjacent bridges to $G_i$ and denote the obtained graph
$G_i'$. We find a weak  $3$-edge-coloring of $G_i'$ with the bridge
ends regular.

If $G_i$ is only an isolated vertex, we color the three edges (bridges)
of $G_i'$ by three different colors. Otherwise, there are two cases to consider, 
(a) only the bridge $b_i$ is attached to $G_i'$, (b) there are some other bridges.

(a) 
The end of the bridge $b_i$ is not a bipartite end.
By Lemma \ref{proposition:evencycle}, there exists an even cycle passing thorugh the end of
the bridge. We color the edges of the cycle alternately $1$ and $2$,
and all the other edges (including the bridge $b_i$) by $0$.

\begin{figure}
\begin{center}
\includegraphics{block}
\caption{Block with bridges attached to it.}
\label{fig:block}
\end{center}
\end{figure}

(b) 
Denote $u_1 v_1, u_1 v_2, \dots, u_m v_m$, $m > 1$ the
bridges of $G_i'$, where vertices $u_1, u_2, \dots, u_m$ are of degree $1$.
(See Figure \ref{fig:block}.)
For each bridge end $u_j$ take shortest path $\pi_j$ 
from $u_j$ to some other $u_l$, $l \neq j$. Clearly, any other $u_r$
nor $v_r$ does not lie on the path $\pi_j$ ($r\neq j$, $r\neq l$).

We start with all-zero coloring $\phi_0$ and 
construct a sequence of colorings $\phi_1, \phi_2, \dots, \phi_m$.
If $v_j$ is a regular vertex in
$\phi_{j-1}$ we leave the coloring as was, $\phi_j := \phi_{j-1}$.
On the other hand, if $v_j$ is a weak vertex in $\phi_{j-1}$ we recolor along the path $\pi_j$ as
follows: We construct an auxiliary coloring $\psi_j$ that is all-zero
except on $\pi_j$, where we label the edges $1,2,1,2,\dots$ or
$2,1,2,1, \dots$. Than we set $\phi_j := \phi_{j-1} + \psi_j$.
The coloring $\psi_j$ can be choosen in such way that it will make both
$v_j$ and $v_l$ regular in $\phi_j$.
(If $v_l$ is singular, both possibilities for $\psi$ are fine. But
when $v_l$ is regular in $\phi_{j-1}$, only of them will do good, the
other possibility makes $v_l$ a weak vertex.) Adding $\psi_j$ to a weak
$\phi_{j-1}$ coloring results in correct weak coloring $\phi_j$,
because at any vertex $w$ lying on $\pi_j$ (except the ends $u_j,
u_l$) the sum of colors in $\Z_3$
of the three edges $e_1, e_2, e_3$ adjacent to $w$ still remains zero.
Indeed,
\begin{equation*}
\begin{split}
\phi_j(e_1)+\phi_j(e_2)+\phi_j(e_3) &= (\phi_{j-1}(e_1)+1) + (\phi_{j-1}(e_2)+2) + \phi_{j-1}(e_3) \\
&= \phi_{j-1}(e_1) + \phi_{j-1}(e_2) + \phi_{j-1}(e_3) = 0.
\end{split}
\end{equation*}


\begin{figure}
\begin{center}
\includegraphics{12path}
\caption{Recoloring along the path $\pi_j = u_j v_j \leadsto v_l u_l$.}
\end{center}
\end{figure}

It remains to combine the colorings of the individual $G_i'$s. 
This is done conceptualy in the same way as in Theorem \ref{theorem:general-bridges}.
We leave colors of edges of $G_1'$ untouched. If the colorings of $G_1'$
and $G_2'$ assign different colors to the bridge $b_2$, we can permute the
colors of $G_2'$ to make them equal. In this manner we succesively add
all the $G_i'$s $i=2,\dots,k$.
\end{proof}

Theorem \ref{theorem:general-bridgeless} and Lemma 
\ref{lemma:affine-bridges} are building stones for our main result,
that all graphs without bipartite ends are colorable
by $AG(n,3)$ = $\Z_3 \times \Z_3 \times \dots \times \Z_3$, $n \ge 3$.

\begin{theorem}
Every cubic graph without a bipartite end
posseses an $AG(n,3)$-coloring, $n \ge 3$.
\end{theorem}

\begin{proof}
Let $G$ be cubic graph without a bipartite end.
By Theorem \ref{theorem:general-bridges}, $G$ admits a weak
$AG(2,3)$-coloring $\phi$ such that only the bridge ends are singular.
By Lemma \ref{lemma:affine-bridges}, $G$ admits a
weak $\mc T$-coloring $\psi$ such that bridge ends are regular.
The sets of singular vertices of $\phi$ and $\psi$ are disjoint and
hence by Theorem
\ref{theorem:mn} there exist a (non-weak) Steiner coloring by
$AG(2,3)\times \mc T = AG(3,3)$. 
If $n>3$, it suffices to use direct product with an all zero $AG(n-3,3)$-coloring.
\end{proof}

We know that Snarks (including all the graphs with bridges) can not be
$3$-colored.  We have completely characterized the class of
$AG(n,3)$-colorable cubic graphs, $n \ge 3$.  However it is still open
which cubic graphs are $AG(2,3)$-colorable. We know, that there exist
$AG(2,3)$-colorable cubic graphs with bridges, for example on Figure
\ref{fig:aff9-bridge}. We suspect, that the classes of
$AG(2,3)$- and $AG(3,3)$-cororable 
cubic graphs are equal, but we do not know how to prove it.

\begin{figure}
\begin{center}
\includegraphics{aff9-bridge}
\caption{Graph with a bridge colored by $AG(2,3) = \Z_3 \times \Z_3$.}
\label{fig:aff9-bridge}
\end{center}
\end{figure}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%% FANO COLORINGS %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\section{Fano colorings}

In this section we will study the colorings by the Fano plane.
Fano colorings are best handled together with the whole class of
colorings by projective Steiner systems, which in turn are essentialy
nowhere-zero group-valued flows.

We will denote $\overrightarrow E$ the set of darts of a graph. This set contains
two darts corresponding to each edge of the graph, one in each
direction. If $e$ is a dart, we will denote $e^{-1}$ the dart in the opposite 
direction. The set of darts incident with a vertex $v$ (both leaving or
entering $v$) will be denoted $E(v)$.

\begin{definition}[Flow]
Let $G=(E,V)$ be a multigraph and $A$ a finite Abelian group (with additive notation).
Then a function $f: \overrightarrow{E} \to  A$ satisfying
\begin{itemize}
\item $f(e^{-1}) = - f(e)$ for each dart  $e \in \overrightarrow{E}$ 
\item and $\sum_{e \in E(v)} f(e) = 0$ for each vertex $v \in V$ (Kirchhoff's law),
\end{itemize}
is called \emph{$A$-flow} on $G$.
Moreover, if $f(e) \neq 0$ for each dart, the flow is called a \emph{nowhere-zero}.
\end{definition}

If each element of the group is its own inverse, that is $a$=$-a$,
then $f(e) = f(e^{-1})$ and the
orientation of egdes loses its sense. Thus the flow can be treated as
the coloring of the edges only. This is also the case of group $(\Z_2
\times \Z_2 \times \dots \times \Z_2,+)$. 
Due to Kichhoff's law, a projective Steiner coloring is in fact
a nowhere-zero $\Z_2 \times \Z_2 \times \dots \times \Z_2$-flow,
and we will make no distinction between these two. We
utilize the known results about flows, 
of which the theorem of Tutte and the $6$-flow theorem of Seymour are of utmost
importance. The proofs can be found, for example, in the textbook \cite{diestel}.

\begin{theorem}[Tutte]
Let $G$ be a graph and $A$, $B$, $|A| \le |B|$ two Abelian groups.
If $G$ has a nowhere zero $A$-flow, then it has also a nowhere zero
$B$-flow.
\end{theorem}

That means that the existence of a nowhere zero flow depens solely on
the order of the group and does not depend on its structure.
Thefore we just say that $G$ has \emph{$k$-flow}, if 
$G$ admits an $A$-flow for some Abelian group of order $k$.

\begin{theorem}[Seymour]
Any bridgeless graph possesses a nowhere zero $6$-flow.
\end{theorem}

These two results imediately imply the following.

\begin{theorem}
\label{theorem:fano-bridgeless}
Every bridgeless cubic graph is colorable by any nontrivial projective Steiner system.
\end{theorem}

In particular, every bridgeless cubic graph has a coloring by the Fano
plane. However when graph has bridges, only a weak Steiner colorings by the Fano
plane can be guaranteed.  

Weak coloring by the Fano plane in which only the bridge ends are
singular can be obtained from the Lemma \ref{lemma:affine-bridges}.
Except the case of bipartite ends, bridge ends can be made regular in
weak $3$-edge-coloring, and hence also in a weak Fano-coloring.
However, since the Fano plane is not an affine system, we can manage
the bipartite end to be regular in a weak Fano coloring too.

\begin{lemma}\label{lemma:weak-fano}
Let $G$ be a simple cubic graph and let $H$ be block of $G$ with a single
cut-vertex $v$ with the bridge (a half-edge) attached. If $v$ is a bipartite end, then $H$ has a weak coloring by
Fano plane in which $v$ is regular, with any choosen triple of colors
in any choosen order at $v$.
\end{lemma}

\begin{proof}
Fano plane is $2$-point-transitive.  (That means that for any four
points $x,y,z,w$ of the Fano plane there is an authomorphism of the
Fano plane mapping $x$ to $y$ and $z$ to $w$.) This is clear from
that the Fano plane can be seen as a projective plane.  Thus if
we find any weak coloring satisfying the theorem, we can apply
suitable automorphism to the coloring and obtain any desired triple of
colors at $v$ in any order.

We proceed by induction on the number vertices of $H$.  Denote by $x,y$
the neighbours of $v$ in $H$.  Denote by $H'$ the graph obtained from $H$
by removing the bridge and suppressing $v$ and denote $h$ the
$xy$-edge created by the suppresion of $v$.


\begin{figure}
\begin{center}
\includegraphics{k33}
\caption{$K_{3,3}$ with a subdivided edge weakly colored by the Fano plane.}
\label{fig:k33}
\end{center}
\end{figure}
The graph $H$ with the least number of vertices is $K_{3,3}$ with a
subivided edge and bridge attached. Its weak coloring is depicted on
Figure \ref{fig:k33}. This forms the basis of the induction.

The graph $H'$ is a bipartite cubic graph with partite sets, say, $X$ and $Y$,
$x \in X$, $y \in Y$. $H'$ has three edge-disjoint $1$-factors $F_1,
F_2, F_3$, $h \in F_1$.  Color the edges of $F_1, F_2, F_3$
respectively by the colors $(0,1,1)$, $(0,0,1)$ and $(0,1,0)$.  This
coloring forms a nowhere-zero $4$-flow in $H'$.  We first transform
this to 'not-yet-a-coloring' of $H$: Color the bridge at $v$ by
$(0,1,1)$, the edge $vx$ by $(1,0,1)$, the edge $vy$ by $(1,1,0)$ and
all other edges by the same color as in $H'$. Note that $v$ and all
other vertices except $x$ and $y$ are regular in this
'not-already-a-coloring'. The vertices $x$ and $y$ are neither regular
nor singular.  Later we will send some flow value along some paths to
correct this anomaly.  

\begin{figure}
\begin{center}
\includegraphics{cycles}
\caption{Graph $H$ (the edges inside the $F_2 \cup F_3$-cycles are not
shown) and corresponding graphs $D$ and $U$. A path 
shown thick in $H$ and the corresponding path in $U$.}
\label{fig:cycles}
\end{center}
\end{figure}
$F_2 \cup F_3$ forms an even $2$-factor of $H'$ i.e. a set of even cycles
covering all vertices.  Direct all edges of $F_1$ from
$X$ to $Y$ and contract cycles of the $2$-factor. We obtain an
Eulerian directed graph $D$. Call $U$ the unoriented version of this
graph. Clearly, $U$ is $2$-edge connected and has cuts of even size
only.  Every path in $U$ (or $D$) corresponds to a path in $H'$ between $F_2
\cup F_3$-cycles; in this path correspondence, we will use only those
$F_1$ edges that connect two distinct $F_2 \cup F_3$-cycles and freely
use all $F_2$- and $F_3$-edges.  (See Figure \ref{fig:cycles}.) This
correspendence of paths in $U$ and $H'$ will be used repeatedly.  We
consider a number of cases:

(a) $U$ has a single vertex only. Then $H'$ is Hamiltionian, with $F_2
\cup F_3$ forming a Hamilton cycle.  Label the vertices along the
Hamilton cycle $v_1, v_2, \dots, v_k, \dots, v_n$, where $x=v_1$ and
$y=v_k$, $1<k \le n$.  Consider the set of vertices $A=\{v_2, v_3,
\dots, v_{k-1}\}$. Clearly $|A \cap X| = |A \cap Y|$. There are two types
of $F_1$-edges incident with the vertices in $A$: edges of the form
$v_i v_j$, $1<i,j<k$, $v_i \in X$, $v_j \in Y$ and edges of the form
$v_i v_j$, $1<i<k<j$.  Since each vertex in $A$ is incident with
exactly one $F_1$-edge and $H'$ is bipartite there  is the same number
of edges of the second form incident with $A \cap X$ and with $A \cap
Y$ .  Hence there is an even number of the edges of the form $v_i
v_j$, $1<i<k<j$.

\begin{figure}
\begin{center}
\includegraphics{hamilton}
\caption{Hamiltonian cycle $C$ in $H'$. Dotted are two important edges
$v_p v_q$ and $v_r v_s$.}
\label{fig:hamilton}
\end{center}
\end{figure}
(a1) Assume that there exists at least two such edges $v_p v_q$ and
$v_r v_s$ in $F_1$, $1<p,r<k<q,s$. Then $C_1 =
v_1,v_2,\dots,v_p,v_q,v_{q+1},\dots,v_n,v_1$ and $C_2 =
v_1,v_2,\dots,v_r,v_s,v_{s+1},\dots,v_n,v_1$  form two cycles through
$x$ and not through $y$. (See Figure \ref{fig:hamilton}.) Divide $C$
into two $yx$-paths $\pi,\rho$, where $\pi$ starts with a $F_2$-edge and
$\rho$ with an $F_3$-edge. Send the value $(1,1,1)$ along $\pi$ and
send the value $(1,0,0)$ along $\rho$. The vertex $y$ becomes
singular. As next, send along $C_1$ the value $(0,0,1)$ and along
$C_2$ the value $(0,1,0)$. As a result the vertex $x$ becomes singular
too. It is easy to see, that no edge receives the color $(0,0,0)$.
Thus we have obtained a valid weak coloring as claimed.
(The assumption for this case holds also for the induction basis (i.e.
$H'=K_{3,3}$) and the colorings obtained there and here are exactly the same.)

(a2) If there is no such edge $v_i v_j$ ($1<i<k<j$), then take longer of
two the $xy$-paths of the Hamilton cycle. Without loss of generality
let $\pi=v_1,v_2,\dots, v_{k-1}, v_k$ be such. Since $G$ is simple,
$\pi$ has length at least $7$. Send the value $(1,1,0)$ along the edge
$xv_2$ and $(1,0,1)$ along the edge $yv_{k-1}$. The vertices $x,y$
become regular.  The colors of the edges $xv_2, yv_{k-1}$ will be distinct
-- $(1,0,0)$ and $(1,1,1)$.  Remove the edges $xv_2$ and $yv_{k-1}$ and take
the component in which $v_2$ and $v_{k-1}$ lie. Add a new vertex $v'$
and a three new edges $v_2v'$, $v'v_{k-1}$ and a bridge (a half-edge)
at $v'$. We have thus formed a smaller block $B$ with bipartite end
$v'$. By induction hypothesis this block is weak Fano-colorable such
that $v'v_2$ receive the same color as $xv_2$ and $v'v_{k-1}$ receive the
same color as $yv_{k-1}$. By removing $v'$ from $B$ and pasting $B$ it to its
original place in $H$ we obtain a weak Fano-coloring.

(b) $U$ has at least $2$ vertices and has a $2$-cut separating $x$ and
$y$.  In $H'$ the edges $h,e$ also form a $2$-cut.  Clearly, $h$ is
one of edges of the cut, denote $e=uw$ the other one. Denote $A,B$ the
separated sets of $H'$; $x,u \in A, y,w \in B$. There exist a
$yu$-paths $\pi$ in $H'$, $e \in \pi$, $h \not\in \pi$.  Send along
$\pi$ the value $(1,0,1)$.  Cutting the $2$-cut and using the same
cut-and-paste construction as in case (a2), we get the desired
coloring.

(c) $U$ has at least $2$ vertices and $x$ and $y$ have been contracted
to a single vertex in $U$. Pick another vertex $u$. 

(c1) If there is $2$-cut in $U$ separating $u$ and $x,y$, then send along
$xw$-path the value $(1,1,0)$ and the value $(1,0,1)$ along $yz$-path,
where $w,z$ are the end vertices of the $2$-cut on same side of the
cut as $u$. Then use the same cut-and-paste construction as in case
(a2).

(c2) Otherwise there are four edge-disjoint $xu$-paths (= $yu$-path) in $U$. From
the pingeon hole principle, among these four paths there must be two paths
$\pi, \rho$, of which the last edges have the same orientation in $D$
(i.e.  both edges are directed either to or out of $u$.)  It means
that the corresponding paths in $H'$ end at some common cycle $C$ of
$F_2 \cup F_3$ and the last vertices $u_1, u_2 \in C$ of $\pi, \rho$
lie in the same partite set.  Take the corresponding path $\pi'$ and
$\rho'$ in $H'$, $\pi'$ a $xu_1$-path and $\rho'$ a $yu_1$-path.  The
vertices $u_1, u_2$ lie on common cycle of $F_2 \cup F_3$, and are in
the same partite set of $H'$.  Send along $\pi'$ the value $(1,1,0)$
and along $\rho'$ the value $(1,0,1)$. The vertices $x,y$ become
regular.  Divide $C$ into two paths $u_1u_2$-path and send along the
path the values $(1,0,0)$ and $(1,1,1)$ suitably such that $u_1, u_2$
become singular.

(d) $U$ has at least $2$ vertices, $x$ and $y$ have not been
contracted to a single vertex in $U$, and there is no $2$-cut
separating $x$ and $y$. Then there is a directed $xy$-path $\pi$ in
$D$ not using the edge $h$.  Let $\pi'$ be the corresponding $yu-$path
in $H'$, where $u$ is on the same $F_2 \cup F_3$-cycle as $x$.  Send
along $\pi'$ the value $(1,0,1)$. Then divide the $F_2 \cup F_3$ cycle
into two $xu$-paths and continue as in case (c2).

In all cases no edge receives the color $(0,0,0)$, hence statement of
the Lemma is established.
\end{proof}

In the paper \cite{skoviera1} is proved, that every cubic graph 
without series-parallel end
is colorable by a Steiner system of order $381$. Our main result of this
paper improves this -- we show that every such graph is colorable by
a Steiner system of order $21$.

\begin{theorem}
Every cubic graph with no series-parallel end 
(in particular every simple cubic graph) is $\mc T \times \mc F$-colorable.
\end{theorem}

\begin{proof}
If the graph has parallel edges reduce them, a self-loop can not arise.

Decompose the graph into 2-edge-connected components (i.e. blocks or
isolated vertices) and attach all ajdacent bridges to the each
component.  We construct  weak $3$-edge-coloring and weak
Fano-coloring of each of these components.  Since both the trivial
Steiner system and Fano plane are point-transitive these colorings can be
combined to a single weak $\mc T \times \mc F$-coloring of the whole
graph.  It remains to manage any vertex to be regular in either
$3$-coloring or Fano-coloring.

Let $H$ be any $2$-edge-connected component of $G$ with bridges
attached. We consider a few cases: 

(a) If $H$ has no bridges, then it has strong Fano-coloring and all-singular
$3$-edge-coloring.

(b) If $H$ has at least two bridges or $H$ has only one bridge and the
bridge end is not a bipartite one, then $H$ has a weak Fano-coloring
in which only bridge ends are singular and a weak $3$-edge-coloring in
which the bridge ends are regular.

(c) If $H$ has only one bridge and the bridge end is a bipartite one,
then it has a weak Fano-coloring in which the bridge end is regular.
Since after removing the bridge and suppressing the $2$-valent vertex
the component becomes bipartite, hence $H$ has $3$-edge-colororing in
which only the bridge end is singular.

In any of the three cases all the vertices of $G$ are regular in at least one
of the two colorings: Fano-coloring or $3$-edge-coloring.
\end{proof}

%\section{Algorithmic aspects}
%
%In this section we show, that most of the Steiner colorings presented
%earlier can be obtained in polynomial time. In fact the only 
%exception is the $3$-coloring of given cubic graph. In the paper
%\cite{holyer} Holyer shows that it is an NP-complete problem to
%determine whether the chromatic index of a cubic graph is 3.
%
%\begin{theorem}
%Let $\mc S$ be a nontrivial affinne or projective Steiner system.
%There exist an polynomial algorithm which colors given bridgeless
%cubic graph by $\mc S$.
%\end{theorem}
%
%\begin{proof}
%Detailed proof of this theorem would be rather tedious.
%For projective systems is the algorithm essentialy the same as the $6$-flow algorithm
%in \cite{younger}.  For affine systems it suffices to follow the proof
%of the coloring theorem in \cite{skoviera2}. 
%The first crucial step is to find a perfect matching, this can be done
%in polynomial time using the well known Edmonds algorithm. Finding
%$2$-cuts can be done using Floyd-Fulkerson algorithm.
%
%The second crucial step is to find a $4$-flow in a $4$-edge-connected graph, which can be
%accomplished by finding two edge disjoint spanning trees (or forests)
%of the graph. Algorithms for finding edge-disjoint spanning trees were
%widely studied. The algorithm can be found, for example, in Kameda
%\cite{kameda}.
%\end{proof}
%
%\begin{theorem}
%There exists an polynomial algorithm that 
%for given cubic graph computes a $\mc {T \times F}$-coloring or
%reports that no Steiner colorings exist.
%\end{theorem}
%
%\begin{proof}
%Again we only sketch the proof. We reduce the graph using the
%reductions of double and triple edges. If a self-loop arises we report
%that no coloring exists and stop. Otherwise we decompose the graph
%into blocks. We remove the bridges and suppress $2$-valent vertices. 
%
%In each the component obtained using using DFS we color the vertices
%by two colors, such that colors will form a valid coloring of the DFS
%tree. If there is back edge connecting two vertices with same color,
%we have an odd cycle. Otherise we know that the component is
%bipartite. This can be again done in linear time.
%
%In case of bipartite component we find three perfect matchings by
%Edmonds algorithm and find Fano-coloring as decribed in Lemma \ref{lemma:weak-fano}
%($2$-cuts are found using Ford-Fulkerson algorithm).
%
%Otherwise we use use the algorithm based on $6$-flow algorithm to
%compute the Fano-coloring. The algorithm for a weak $3$-edge-coloring is decribed 
%in the coloring Lemma \ref{lemma:affine-bridges} in detail.
%\end{proof}

\section{A note on Berge-Fulkerson conjecture}

In paper \cite{skoviera3} is the Berge-Fulkerson conjecture given:
\begin{conjecture}[Berge-Fulkerson]
Every bridgeless cubic graph has six perfect matchings, such that
each edge of the graph lies in exactly two of the matchings.
\end{conjecture}

\begin{figure}
\begin{center}
\includegraphics{projective15}
\caption{The projective Steiner system $PG(3,2)$. Not all points and triples are shown.}
\label{fig:projective15}
\end{center}
\end{figure}

This conjecture gives arise to an unusual combinatorial representation
of the projective Steiner triple system $PG(3,2)$: Let us have six
element set $M=\{a,b,c,d,e,f\}$.  (An element of $M$ represents one
of the six perfect matchings.)
There are $\binom{6}{2} = 15$ of $2$-element subsets of $M$, these 15
subsets will form the point set of $PG(3,2)$. The triples will be of
two types, either $\{\{x,y\},\{y,z\},\{x,y\}\}$ or
$\{\{u,v\},\{w,x\},\{y,z\}\}$, where $u,v,w,x,y,z$ are distinct
elements of $M$. There are $20$ triples of the first type and $15$ of
the second type.  We give the isomorphism with standard  $\Z_2 \times \Z_2 \times
\Z_2 \times \Z_2 - \{(0,0,0,0)\}$ representation of $PG(3,2)$
explicitly:
\begin{eqnarray*}
\{a,b\} \mapsto (1,1,0,0), &\{b,c\} \mapsto (0,1,1,0), & \{c,e\} \mapsto (0,0,1,0), \\
\{a,c\} \mapsto (1,0,1,0), &\{b,d\} \mapsto (0,1,0,1), & \{c,f\} \mapsto (1,1,0,1), \\
\{a,d\} \mapsto (1,0,0,1), &\{b,e\} \mapsto (0,1,0,0), & \{d,e\} \mapsto (0,0,0,1), \\
\{a,e\} \mapsto (1,0,0,0), &\{b,f\} \mapsto (1,0,1,1), & \{d,f\} \mapsto (1,1,1,0), \\
\{a,f\} \mapsto (0,1,1,1), &\{c,d\} \mapsto (0,0,1,1), & \{e,f\} \mapsto (1,1,1,1).
\end{eqnarray*}

Theorem \ref{theorem:fano-bridgeless} assures us, that every bridgeless
cubic graph can be colored by $PG(3,2)$. However the point here is to
find a $PG(3,2)$-coloring using only the triples of the second type.
A Steiner coloring by $PG(3,2)$ using only the triples of the second
type corresponds to the six perfect matchings from the conjecture
and vice versa.  

The first result of this kind is given in the paper \cite{skoviera3}
saying, that only six of the seven triples of the Fano plane suffice
in a Fano-coloring of a bridgeless cubic graph. In addition, a connection to
another conjecture of Fan and Raspaud is given there.

\section{Conclusion}
In the paper \cite{skoviera1} is given the definition of the Steiner chromatic
number. For given cubic graph $G$ the \emph{Steiner chromatic
number} is the least number $n$ such there exists a Steiner triple
system of order $n$ which colors the graph $G$.

Steiner chromatic number of graphs with a series-parallel end is
infinite.  Every bridgeless cubic graph has Steiner chromatic number
either $3$ or $7$ depending on whether it is $3$-edge-colorable or not.
We have shown that every cubic graph with no series-parallel end has
Steiner chromatic number at most $21$.

The graphs with a biparite end have Steiner chromatic number more than
$9$, i.e. at least $13$. There exist only two unisomorphic Steiner
systems of order $13$. Using a computer we have successfully colored some
cubic graphs with a bipartite end by both of these Steiner systems.  For example,
we have colored two copies of $K_{3,3}$ with a subdivided edge and
linked with a bridge. This supports the conjecture given in the paper
\cite{skoviera2}.

\begin{conjecture}
If $G$ is a simple cubic graph and $\mc S$ a non-projective Steiner
triple system, then $G$ fails to have an $S$-coloring only if $S$ is
affine and $G$ has a bridge with bipartite end.
\end{conjecture}

That means, we conjecture that both the Steiner systems of order $13$
color every cubic graph with no series-parallel end. However the
structure of both of these Steiner systems lack the algebraic beauty of affine or
projective systems making understanding of colorings by these
systems much worse.

\section{Acknowledgements}

I would like to thank to my advisor Martin \v Skoviera for directing
me during the research and fruitful discussions with him.  Without
his support this work would never have been written.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% BIBLIOGRAPHY %%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\newpage

\begin{thebibliography}{99}

\bibitem{diestel} R. Diestel, 
\emph{Graph Theory} (Second Edition), Springer Verlag, 2000

\bibitem{skoviera1} M. Grannel, T. Griggs, M. Knorr and M. \v Skoviera, 
\emph{A Steiner triple system which colours all cubic graphs},
Journal of Graph Theory, Volume 46, Issue 1, May 2004, 15-24

\bibitem{skoviera2} F. Holroyd and M. \v Skoviera, 
\emph{Colouring of cubic graphs by Steiner triple systems}, 
Journal of Combinatorial Theory, Series B, Volume 91, Issue 1, May
2004, 57-66

\bibitem{skoviera3} E. Ri\v canyov\'a and M. \v Skoviera,
\emph{Fano colourings of cubic graphs and the Fulkerson Conjecture}, 2003

\bibitem{younger} D. H. Younger, 
\emph{Integer flows}, 1983, 
Journal of Graph Theory, Volume 7, 349-357

\bibitem{jaeger} F. Jaeger, 
\emph{Flows and generalized coloring theorems in graphs},
Journal of Combinatorial Theory, Series B, Volume 26, No. 2, April
1979, 205-216

\bibitem{holyer} Ian Holyer,
\emph{The NP-completness of edge-coloring},  SIAM Journal of Computing
Volume 10, No. 4, November 1981, 718-720

\bibitem{kameda} T. Kameda,
\emph{On maximally distant spanning trees of a graph}, 1976 Computing, 17,
115--119


\end{thebibliography}


\end{document}

