Steiner Colorings of Cubic Graphs

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

Advisor: RNDr. Martin Škoviera, PhD.

Bratislava, April 2004 Dávid Pál

1 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 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.

2 Steiner triple systems and colorings

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

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

Proposition 2. Let S be a Steiner triple system of order n. Then

n ≡ 1 or 3 (mod 6).

Proof. Choose an arbitrary fixed point v. There are n − 1 pairs of the form {u, v}, u ≠ 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.

The converse is also true. That is, if n ≥ 3 and n mod 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, … and systems of other orders do not.

The simplest Steiner system is the trivial Steiner system of order 3 consisting of only one triple. We will denote it by the letter T . The smallest nontrivial Steiner triple system is the so called Fano plane depicted on Figure 1. It is the only system of order 7. As its point set we take nonzero vectors over the field ℤ_{2} of length three ℤ_{2} × ℤ_{2} × ℤ_{2} − {(0, 0, 0)}. As the set of

Figure 1: The Fano plane. Straight lines and the circle form the triples.

triples we take all triples {a, b, c} where a + b + c = (0, 0, 0). We will denote the Fano plane by F.

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

Theorem 3 (2n+1-construction). For each Steiner triple system of order n there exists a Steiner triple system of order 2n + 1.

Proof. Let S = (P, T) be any Steiner system of order n. Let us take an isomorphic copy of the system S, which we will denote S′ = (P′, T′) together with the isomorphism v ↦ v′ for every point v ∈ P. Further let x be a new (2n + 1)-th point. Then S′′ = (P′′, T′′), P′′ = P ∪ P′ ∪ {x} and

T′′ = T ∪ {{u, v′, w′} | {u, v, w} ∈ T } ∪ {{v, v′, x} | v ∈ P }

is Steiner triple system of order 2n + 1.

Starting with the trivial Steiner triple system and successively using 2n+ 1-construction we form the class of the so called projective Steiner systems. They can be easily algebraically described as the projective spaces over the field ℤ_{2}. After n − 1 contructions we get a system isomorphic to the n dimensional projective space over the field ℤ_{2} denoted by P G(n, 2). It has order 2^{n+1} − 1 and the point set is

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

The set of triples is formed by all the triples {a, b, c} where a + b + c = (0, 0, …, 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.

Theorem 4 (Direct product). Let S = (P_{S}, T_{S}) and R = (P_{R}, T_{R}) be two Steiner triple systems of order m and n respectively. Then there exists a Steiner triple system of order mn.

Proof. As the point set of the system we take P_{S} ×P_{R}. The triples are formed as follows

{{(s_{1}, r), (s_{2}, r), (s_{3}, r)} | {s_{1}, s_{2}, s_{3}} ∈ T_{S}, r ∈ P_{R}} ∪ {{(s, r_{1}), (s, r_{2}), (s, r_{3})} | s ∈ P_{S}, {r_{1}, r_{2}, r_{3}} ∈ T_{R}} ∪ {{(s_{1}, r_{1}), (s_{2}, r_{2}), (s_{3}, r_{3})} | {s_{1}, s_{2}, s_{3}} ∈ T_{S}, {r_{1}, r_{2}, r_{3}} ∈ T_{R}}.

We will denote S ×R the resulting Steiner triple system from the preceding theorem. Of course, this construction can be easily generalized to more than two systems S_{1}, S_{2}, …, S_{k} forming more complex system S_{1} ×S_{2} ×⋯× S_{k}.

As with the 2n + 1-construction, direct product of trivial Steiner systems gives us the family of the affine Steiner systems. Again, these can be easily algebraically described as the affine spaces over the field ℤ_{3}. The Steiner system

\underbrace{T × T × ⋯ × T}_{n−times}

is isomorphic to the affine space AG(n, 3). Its points set is

\underbrace{ℤ_{3} × ℤ_{3} × ⋯ × ℤ_{3}}_{n−times}

and the triples are of the form {a, b, c}, a + b + c = 0, a ≠ b, b ≠ c, a ≠ 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 P G—meaning affine and projective geometry—are used in both geometrical and combinatorial design literature.

Definition 5. Let G = (V, E) be cubic graph and S = (P, T) a Steiner triple system. A Steiner coloring is a map ϕ : E → P, such that the colors ϕ(e_{1}), ϕ(e_{2}), ϕ(e_{3}) of the three edges e_{1}, e_{2}, e_{3} meeting at any vertex form a triple of S.

Figure 2: Affine plane AG(2, 3). Straight lines and curves form the triples.

Definition 6. Let G = (V, E) be cubic graph and S = (P, T) a Steiner triple system. A weak Steiner coloring is a map ϕ : E → P, such that the colors ϕ(e_{1}), ϕ(e_{2}), ϕ(e_{3}) of the three edges e_{1}, e_{2}, e_{3} meeting at any vertex either form a triple of S or ϕ(e_{1}) = ϕ(e_{2}) = ϕ(e_{3}).

A (weak) coloring by a Steiner triple system S will be called a (weak) S-coloring, for short. There is no difference between a 3-edge-coloring and a 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 regular and the latter vertices singular. (Holroyd and Škoviera [3] 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.

Theorem 7. Let G be a cubic graph, let S, R be two Steiner triple systems, and finally let ϕ be a weak S-coloring and ψ be a weak R-coloring of G. Then there exists a S × R-coloring such the set of singular vertices is the intersection of the sets of singular vertices of ϕ and ψ.

Proof. Let us construct the coloring χ of the graph G by the system S × R as the cartesian product of the colorings ϕ and ψ, that is

χ(e) = (ϕ(e), ψ(e)), e ∈ E(G).

Look at three edges e_{1}, e_{2}, e_{3} meeting at any vertex v ∈ G. If v is regular in one or both of the colorings ϕ, ψ i.e. ϕ(e_{1}), ϕ(e_{2}), ϕ(e_{3}) is triple of S or

Figure 3: Reduction of a double edge.

ψ(e_{1}), ψ(e_{2}), ψ(e_{3}) is triple of R or both are, then χ(e_{1}) = (ϕ(e_{1}), ψ(e_{1})), χ(e_{2}) = (ϕ(e_{2}), ψ(e_{2})), χ(e_{3}) = (ϕ(e_{3}), ψ(e_{3})) is triple of S × R and v is regular in the coloring χ.

If v is singular in both ϕ and ψ, that is ϕ(e_{1}) = ϕ(e_{2}) = ϕ(e_{3}) and ψ(e_{1}) = ψ(e_{2}) = ψ(e_{3}), then χ(e_{1}) = (ϕ(e_{1}), ψ(e_{1})) = χ(e_{2}) = (ϕ(e_{2}), ψ(e_{2})) = χ(e_{3}) = (ϕ(e_{3}), ψ(e_{3})) and v is singular in χ.

In any case, χ is a correct weak Steiner coloring.

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.

3 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

Proposition 8 (Reduction of a triple edge). Let 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 S-colorable if and only if G is.

Proof. Clearly, any S-coloring of G is also a S-coloring of G′. Conversely, any S-coloring of G′ can be extended to a coloring of G′ – it suffices to color the triple edge xy by any triple of S.

Proposition 9 (Reduction of a double edge). Let 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 S-colorable if and only if G is.

Proof. Let be u, v be neighbouring vertices of the double edge xy; ux, yv ∈ E(G). (See Figure 3.) Let us have any 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 S and assign the color c_{1} to both the edges ux and yv.

Conversely, let us have a 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.

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

Definition 10. A series-parallel graph is recursively defined as follows:

• The disjoint union of any number of the graphs K_{1} and K_{2} is seriesparallel.

• A graph obtained from a series-parallel graph by subdivision of an edge is series-parallel.

• A graph obtained from a series-parallel graph by creating a parallel edge is series-parallel.

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.

Definition 11. Let G be a cubic graph. An end vertex v of a bridge is called a series-parallel end, if after removing the bridge and supressing v the component containing v becomes series-parallel.

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 [2]. 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 [3].

Figure 4: Connecting G′_{i} = G_{6} to preceding components.

Theorem 12. Every bridgeless cubic graph admits S-coloring, for any nontrivial Steiner system S.

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.

Theorem 13. Let S be any non-trivial point-transitive Steiner system. Every cubic graph has a weak S-coloring where the singular vertices are exactly the end-vertices of bridges.

Proof. After removing bridges from the graph 2-connected components and isolated vertices remain. Let G_{1}, G_{2}, …, G_{k} be ordering of both isolated vertices and 2-connected components such, that G_{i} connects to G[G_{1}, G_{2}, …, 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 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 S-coloring of G′′_{i} in which only the bridge ends are singular. Moreover since S is point-transitive, the coloring can be choosen with any prescribed color of b_{i}.

We will succesively color G′′_{1} ∪G′′_{2} ∪⋯∪G′′_{i}, for i = 1, 2, …, k. Clearly G′′_{1} can be colored. The rest of the sequence can be accomplished by succesively adding G′′_{i} to G′′_{1} ∪ G′′_{2} ∪ ⋯ ∪ G′′_{i−1}. Since G′′_{i} and and G′′_{1} ∪ G′′_{2} ∪ ⋯ ∪ 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} ∪ G′′_{2} ∪ ⋯ ∪ G′′_{i} ∪ G′′_{i+1} is easily established.

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.

4 Affine colorings

Definition 14. Let G be a cubic graph. And end vertex v of a bridge is called a bipartite end, if after removing the bridge and supressing v the component containing v becomes bipartite.

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.

Proposition 15. In a cubic graph each bipartite end is a singular vertex of any weak affine coloring.

Proof. Let G be cubic graph with the bipartite end v. For the purpose of contradiction suppose that ϕ : E(G) → ℤ_{3} × ℤ_{3} × ⋯ × ℤ_{3} is a weak coloring of G by an affine Steiner triple system.

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 ∈ X, y ∈ Y. The colors of the three edges e_{1}, e_{2}, e_{3} at any vertex of H satisfy ϕ(e_{1}) + ϕ(e_{2}) + ϕ(e_{3}) = (0, 0, …, 0), even in case of singular vertex. Using this fact, a little algebra

(0, 0, …, 0) = ∑_{e∈E(H)}(ϕ(e) − ϕ(e))

= ϕ(vy) − ϕ(vx) + ∑_{\begin{matrix}x′∈X \\ z∈V (H−X) \end{matrix}} ϕ(x′z) − ∑_{\begin{matrix}y′∈Y \\ z∈V (H−Y) \end{matrix}} ϕ(y′z)

= ϕ(vy) − ϕ(vx)

Figure 5: Even cycle through non-bipartite end is either π_{1}ρ_{1}π_{2} or π_{1}ρ_{2}π_{2}.

shows that ϕ(vx) = ϕ(vy) and hence v is singular.

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.

Proposition 16. Let G be cubic graph and let H be block of G with a single cut-vertex v.

1. The vertex v is bipartite end.

2. Every cycle through v in H is odd.

Proof. The implication 1 ⇒ 2 clearly holds. For 2 ⇒ 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 π_{1}, π_{2} from v to some two distinct vertices x and y of C. Divide the cycle C into two paths ρ_{1}, ρ_{2} between x and y. (See Figure 5.) Then both π_{1}ρ_{1}π_{2} and π_{1}ρ_{2}π_{2} are cycles through v and have different parity. Therefore there is an even cycle through v contradicting 2.

Clearly, if v is not a bipartite end, then in H there exists an even cycle cycle through v.

Lemma 17. 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.

Figure 6: Block with bridges attached to it.

Proof. Decompose the graph into 2-connected components and isolated vertices. Let G_{1}, G_{2}, …, 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}, …, 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 16, 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.

(b) Denote u_{1}v_{1}, u_{1}v_{2}, …, u_{m}v_{m}, m > 1 the bridges of G′_{i}, where vertices u_{1}, u_{2}, …, u_{m} are of degree 1. (See Figure 6.) For each bridge end u_{j} take shortest path π_{j} from u_{j} to some other u_{l}, l ≠ j. Clearly, any other u_{r} nor v_{r} does not lie on the path π_{j} (r ≠ j, r ≠ l).

We start with all-zero coloring ϕ_{0} and construct a sequence of colorings ϕ_{1}, ϕ_{2}, …, ϕ_{m}. If v_{j} is a regular vertex in ϕ_{j−1} we leave the coloring as was, ϕ_{j} := ϕ_{j−1}. On the other hand, if v_{j} is a weak vertex in ϕ_{j−1} we recolor along the path π_{j} as follows: We construct an auxiliary coloring ψ_{j} that is all-zero except on π_{j}, where we label the edges 1, 2, 1, 2, … or 2, 1, 2, 1, . . .. Than we set ϕ_{j} := ϕ_{j−1} + ψ_{j}. The coloring ψ_{j} can be choosen in such way that it will make both v_{j} and v_{l} regular in ϕ_{j}. (If v_{l} is singular, both possibilities for ψ are fine. But when v_{l} is regular in ϕ_{j−1}, only of them will do good, the other possibility makes v_{l} a weak vertex.) Adding ψ_{j} to a weak ϕ_{j−1} coloring results in correct weak coloring ϕ_{j}, because at any vertex w lying on

Figure 7: Recoloring along the path π_{j} = u_{j}v_{j} ⇝ v_{l}u_{l}.

π_{j} (except the ends u_{j}, u_{l}) the sum of colors in ℤ_{3} of the three edges e_{1}, e_{2}, e_{3} adjacent to w still remains zero. Indeed,

\begin{aligned}ϕ_{j}(e_{1}) + ϕ_{j}(e_{2}) + ϕ_{j}(e_{3}) & = (ϕ_{j−1}(e_{1}) + 1) + (ϕ_{j−1}(e_{2}) + 2) + ϕ_{j−1}(e_{3}) \\ & = ϕ_{j−1}(e_{1}) + ϕ_{j−1}(e_{2}) + ϕ_{j−1}(e_{3}) = 0. \end{aligned}

It remains to combine the colorings of the individual G′_{i}s. This is done conceptualy in the same way as in Theorem 13. 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, …, k.

Theorem 12 and Lemma 17 are building stones for our main result, that all graphs without bipartite ends are colorable by AG(n, 3) = ℤ_{3} ×ℤ_{3} ×⋯×ℤ_{3}, n ≥ 3.

Theorem 18. Every cubic graph without a bipartite end posseses an AG(n, 3)- coloring, n ≥ 3.

Proof. Let G be cubic graph without a bipartite end. By Theorem 13, G admits a weak AG(2, 3)-coloring ϕ such that only the bridge ends are singular. By Lemma 17, G admits a weak T -coloring ψ such that bridge ends are regular. The sets of singular vertices of ϕ and ψ are disjoint and hence by Theorem 7 there exist a (non-weak) Steiner coloring by AG(2, 3) × T = AG(3, 3). If n > 3, it suffices to use direct product with an all zero AG(n − 3, 3)-coloring.

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

Figure 8: Graph with a bridge colored by AG(2, 3) = ℤ_{3} × ℤ_{3}.

cubic graphs, n ≥ 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 8. 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.

5 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).

Definition 19 (Flow). Let G = (E, V) be a multigraph and A a finite Abelian group (with additive notation). Then a function f : \overrightarrow{E} → A satisfying

• f(e^{−1}) = −f(e) for each dart e ∈ \overrightarrow{E}

• and ∑_{e∈E(v)} f(e) = 0 for each vertex v ∈ V (Kirchhoff’s law),

is called A-flow on G. Moreover, if f(e) ≠ 0 for each dart, the flow is called a nowhere-zero.

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 (ℤ_{2} × ℤ_{2} × ⋯ × ℤ_{2}, +). Due to Kichhoff’s law, a projective Steiner coloring is in fact a nowhere-zero ℤ_{2} × ℤ_{2} × ⋯ × ℤ_{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 [1].

Theorem 20 (Tutte). Let G be a graph and A, B, |A| ≤ |B| two Abelian groups. If G has a nowhere zero A-flow, then it has also a nowhere zero B-flow.

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 k-flow, if G admits an A-flow for some Abelian group of order k.

Theorem 21 (Seymour). Any bridgeless graph possesses a nowhere zero 6-flow.

These two results imediately imply the following.

Theorem 22. Every bridgeless cubic graph is colorable by any nontrivial projective Steiner system.

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 17. 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.

Lemma 23. 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.

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 Figure 9: K_{3,3} with a subdivided edge weakly colored by the Fano plane.

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.

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 9. This forms the basis of the induction.

The graph H′ is a bipartite cubic graph with partite sets, say, X and Y, x ∈ X, y ∈ Y. H′ has three edge-disjoint 1-factors F_{1}, F_{2}, F_{3}, h ∈ 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.

F_{2} ∪ 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} ∪ F_{3}-cycles; in this path correspondence, we will use only those F_{1} edges that connect two distinct F_{2} ∪ F_{3}-cycles and freely use all F_{2}- and F_{3}-edges. (See Figure 10.) This correspendence of paths in U and H′ will be used repeatedly. We consider a number of cases:

Figure 10: Graph H (the edges inside the F_{2} ∪ F_{3}-cycles are not shown) and corresponding graphs D and U. A path shown thick in H and the corresponding path in U.

Figure 11: Hamiltonian cycle C in H′. Dotted are two important edges v_{p}v_{q} and v_{r}v_{s}.

(a) U has a single vertex only. Then H′ is Hamiltionian, with F_{2} ∪ F_{3} forming a Hamilton cycle. Label the vertices along the Hamilton cycle v_{1}, v_{2}, …, v_{k}, …, v_{n}, where x = v_{1} and y = v_{k}, 1 < k ≤ n. Consider the set of vertices A = {v_{2}, v_{3}, …, v_{k−1}}. Clearly |A ∩ X| = |A ∩ 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} ∈ X, v_{j} ∈ 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 ∩ X and with A ∩ Y . Hence there is an even number of the edges of the form v_{i}v_{j}, 1 < i < k < j.

(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}, …, v_{p}, v_{q}, v_{q+1}, …, v_{n}, v_{1} and C_{2} = v_{1}, v_{2}, …, v_{r}, v_{s}, v_{s+1}, …, v_{n}, v_{1} form two cycles through x and not through y. (See Figure 11.) Divide C into two yx-paths π, ρ, where π starts with a F_{2}-edge and ρ with an F_{3}-edge. Send the value (1, 1, 1) along π and send the value (1, 0, 0) along ρ. 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 π = v_{1}, v_{2}, …, v_{k−1}, v_{k} be such. Since G is simple, π 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_{2}v′, 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 ∈ A, y, w ∈ B. There exist a yu-paths π in H′, e ∈ π, h ∉ π. Send along π 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 π, ρ, 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} ∪ F_{3} and the last vertices u_{1}, u_{2} ∈ C of π, ρ lie in the same partite set. Take the corresponding path π′ and ρ′ in H′, π′ a xu_{1}-path and ρ′ a yu_{1}-path. The vertices u_{1}, u_{2} lie on common cycle of F_{2} ∪ F_{3}, and are in the same partite set of H′. Send along π′ the value (1, 1, 0) and along ρ′ the value (1, 0, 1). The vertices x, y become regular. Divide C into two paths u_{1}u_{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 π in D not using the edge h. Let π′ be the corresponding yu−path in H′, where u is on the same F_{2} ∪ F_{3}-cycle as x. Send along π′ the value (1, 0, 1). Then divide the F_{2} ∪ 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.

In the paper [2] 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.

Theorem 24. Every cubic graph with no series-parallel end (in particular every simple cubic graph) is T × F-colorable.

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 pointtransitive these colorings can be combined to a single weak T × 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.

6 A note on Berge-Fulkerson conjecture

In paper [4] is the Berge-Fulkerson conjecture given:

Conjecture 25 (Berge-Fulkerson). Every bridgeless cubic graph has six perfect matchings, such that each edge of the graph lies in exactly two of the matchings.

Figure 12: The projective Steiner system P G(3, 2). Not all points and triples are shown.

This conjecture gives arise to an unusual combinatorial representation of the projective Steiner triple system P G(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 P G(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 ℤ_{2}×ℤ_{2}×ℤ_{2}×ℤ_{2}−{(0, 0, 0, 0)} representation of P G(3, 2) explicitly:

{a, b} ↦ (1, 1, 0, 0), {b, c} ↦ (0, 1, 1, 0), {c, e} ↦ (0, 0, 1, 0),
{a, c} ↦ (1, 0, 1, 0), {b, d} ↦ (0, 1, 0, 1), {c, f} ↦ (1, 1, 0, 1),
{a, d} ↦ (1, 0, 0, 1), {b, e} ↦ (0, 1, 0, 0), {d, e} ↦ (0, 0, 0, 1),
{a, e} ↦ (1, 0, 0, 0), {b, f} ↦ (1, 0, 1, 1), {d, f} ↦ (1, 1, 1, 0),
{a, f} ↦ (0, 1, 1, 1), {c, d} ↦ (0, 0, 1, 1), {e, f} ↦ (1, 1, 1, 1).

Theorem 22 assures us, that every bridgeless cubic graph can be colored by P G(3, 2). However the point here is to find a P G(3, 2)-coloring using only the triples of the second type. A Steiner coloring by P G(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 [4] 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.

7 Conclusion

In the paper [2] is given the definition of the Steiner chromatic number. For given cubic graph G the 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 [3].

Conjecture 26. If G is a simple cubic graph and 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.

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.

8 Acknowledgements

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

References

[1] R. Diestel, Graph Theory (Second Edition), Springer Verlag, 2000

[2] M. Grannel, T. Griggs, M. Knorr and M. Škoviera, A Steiner triple system which colours all cubic graphs, Journal of Graph Theory, Volume 46, Issue 1, May 2004, 15-24

[3] F. Holroyd and M. Škoviera, Colouring of cubic graphs by Steiner triple systems, Journal of Combinatorial Theory, Series B, Volume 91, Issue 1, May 2004, 57-66

[4] E. Ričanyová and M. Škoviera, Fano colourings of cubic graphs and the Fulkerson Conjecture, 2003

[5] D. H. Younger, Integer flows, 1983, Journal of Graph Theory, Volume 7, 349-357

[6] F. Jaeger, Flows and generalized coloring theorems in graphs, Journal of Combinatorial Theory, Series B, Volume 26, No. 2, April 1979, 205-216

[7] Ian Holyer, The NP-completness of edge-coloring, SIAM Journal of Computing Volume 10, No. 4, November 1981, 718-720

[8] T. Kameda, On maximally distant spanning trees of a graph, 1976 Computing, 17, 115–119