**Generalizations of Tait Coloring Cubic Graphs**

This page is under construction.

A *cubic* graph is one that is regular of degree three. A *Tait** Coloring* assigns one of three colors to
each edge such that no color is repeated at each vertex. Not every bridgeless
cubic graph is Tait colorable. We offer three
generalizations of Tait colorings that may be
achievable for every bridgeless cubic graph.

**Conjecture [J]:** *Every bridgeless graph* G *can have its edges
colored by the edges of the Petersen graph* P *such that three mutually
adjacent edges in* G *receive colors that are mutually adjacent in* P.

Note that every Tait colorable graph can be Petersen colored: use only three Petersen edges. The conjecture is quite strong, as it implies both Cycle Double Cover Conjecture and Fulkerson's Conjecture.

A *Steiner triple system* (STS) is a collection of points and triples
of these points such that every pair occurs in exactly one triple.

**Conjecture [A]:** *Every bridgeless graph* G *can have its edges
colored by points of a Steiner triple system* S *such that three mutually
adjacent edges in* G *receive points in a triple of* S.

The conjecture is true for Tait colorable graphs: use just a single triple.

**Conjecture [A]:** *Let* G *be a bridgeless graph and let* H *be
a group of order at least five. Then the edges of* G *can be colored with
the non-identity elements of* H *such that at each vertex of* G *the
three colors sum to the identity in* H.

This is a type of non-directed flows. The conjecture is true for Tait colorable graphs: just find three distinct elements of
*H* which sum to the identity. This can always be done for a group of
order five or more, hence the restriction. The problem for the Klein four group *Z_2* x *Z_2* is equivalent to Tait coloring.

As far as I know no one has worked on the last two problems. I tested the conjectures on the Petersen graph using several small Steiner Triple Systems and several small groups and found the desired colorings.

**References:**

[A] D. Archdeacon, Coverings of graphs by cycles, *Congressus**
Numerantium* **53** (1986) 7-14.

[J] F. Jaejer, Nowhere-zero flow problems, In: *Selected
Topics in Graph Theory* **3** (L.W. Beineke and
R.J. Wilson Eds.) Academic Press (1988) 71-95.

Submitted by: Dan Archdeacon, Department of Mathematics
and Statistics,

Send comments to *dan.archdeacon@uvm.edu*

August, 1995