Steiner Colorings of Cubic Graphs

Dávid Pál April 22, 2004

Advisor: Martin Škoviera

Comenius University Department of Computer Science

– Typeset by FoilTEX –

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.

Theorem 1 (Vizing, 1964). Cubic graph can be colored by either 3 or 4 colors.

Figure 1: Three-sided prism and the Petersen graph

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

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.

Definition 1. Steiner triple system S is a tuple 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.

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?”.

Examples of Steiner Triple Systems

• Trivial STS, T = ({0, 1, 2}, {{0, 1, 2}}).

• Fano plane F = P G(2, 2) = (ℤ_{2}×ℤ_{2}×ℤ_{2}−{0, 0, 0}, {{x, y, z} | x+y+z = 0})

Figure 2: Fano plane

Graphs without bridges

Holroyd and Škoviera showed that: Theorem 2. Every bridgeless cubic graph can be colored by any non-trivial Steiner system. Theorem 3. Every simple cubic graph can be colored by a particular Steiner system of order 381.

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

Weak colorings

If S_{1}, S_{2}, …, S_{n} are Steiner systems. Then also S_{1} × S_{2} × ⋯ × S_{n} is a Steiner system. The set of points is P (S_{1}) × P (S_{2}) × ⋯ × P (S_{n}). Triples are of the form

{(a_{1}, a_{2}, …, a_{n}), (b_{1}, b_{2}, …, b_{n}), (c_{1}, c_{2}, …, c_{n})},

such that {a_{i}, b_{i}, c_{i}} is a triple of S_{i} or a_{i} = b_{i} = c_{i}, for all i = 1, 2, …, n. And for at least one i holds the former case.

Coloring by the system S_{1} × S_{2} × ⋯ × S_{n} can be understood as a collection of colorings by the individual Steiner systems S_{i}. However in such S_{i}-coloring, we can allow also vertices at which edges of three identical colors meet. We call such colorings weak, and such vertices singular.

Affine colorings

The Steiner system AG(n, 3) = T × T ⋯ × T is called affine.

Figure 3: Affine plane AG(2, 3) = (ℤ_{3} × ℤ_{3}, {{x, y, z} | x + y + z = 0})

Figure 4: A graph with a bridge colored by the affine plane AG(2,3)

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.

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

Figure 5: K_{3,3} with a subdived edge and bridge attached.

0 = ∑_{all edges except the bridge} ϕ(e) − ϕ(e)

= ϕ(vy) − ϕ(vx) + ∑_{edges incident with X} ϕ(e) − ∑_{edges incident with Y} ϕ(e) = ϕ(vy) − ϕ(vx)

Lemma 1. Every simple cubic graph is weak S-colorable such that only the bridge ends are singular, for every non-trivial transitive Steiner system S.

Lemma 2. Every cubic graph without a bridge with a bipartite end is weakly 3-edge-colorable, such that bridge ends are regular.

Theorem 4. Every cubic graph without a bridge with a bipartite end is AG(n, 3)- colorable, for n ⩾ 3.

The idea of the proof is to employ the theorem of Holroyd and Škoviera 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 ⩾ 3.

Projective colorings

The n-dimensional projective Steiner system P G(n, 2) has point set

\underbrace{ℤ_{2} × ℤ_{2} × ⋯ × ℤ_{2}}_{n+1 times} −\{(0, 0, …, 0)\}

and triples

{x, y, z}, x + y + z = (0, 0, …, 0).

Since −1 = 1 in ℤ_{2}, projective colorings are just group-valued nowhere-zero flows. We can employ all known results about flows (Tutte, Seymour):

• Graphs with bridges have no nowhere-zero flow.

• Only the order of the group matters. (The larger the group the better.)

• Every bridgeless graph has a 6-flow.

– Typeset by FoilTEX – 10

Colorings by Fano plane

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

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

Lemma 3. Bipartite cubic graph with a subidivided edge and bridge attached is weakly F-colorable, in such way that the bridge end is regular.

Combining with the Lemma 2, we improve the result of Holroyd and Škoviera.

Lemma 4. Every simple cubic graph is T × F-colorable.

Open problems

Conjecture 1. All graphs without bipartite end are AG(2, 3)-colorable.

Conjecture 2. Any non-projective, non-affine Steiner system colors every simple cubic graph.

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.

Connection with Perfect Matchings

Theorem 5 (Petersen, 1891). Every bridgeless cubic graph has a perfect matching.

Figure 6: Perfect matching in the Petersen graph Conjecture 3 (Fan-Raspaud, 1994). Every bridgeless cubic graph contains three perfect matchings with empty intersection.

Conjecture 4 (Berge-Fulkerson). Every bridgeless cubic graph contains six perfect matchings such that each edge appears in exactly two of them.

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.