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, University of Vermont, Burlington VT 05405 USA.

Send comments to dan.archdeacon@uvm.edu

August, 1995