ARS MATHEMATICA CONTEMPORANEA
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 7 (2014) 161-173
Petersen-colorings and some families of snarks
Jonas Hägglund
Department of Mathematics and Mathematical Statistics, Umeä University SE-901 87 Umeä, Sweden
Eckhard Steffen
Paderborn Institute for Advanced Studies in Computer Science and Engineering, Paderborn University, Zukunftsmeile 1, 33102 Paderborn, Germany
Received 1 December 2011, accepted 19 November 2012, published online 15 April 2013
In this paper we study Petersen-colorings and strong Petersen-colorings on some well known families of snarks, e.g. Blanusa snarks, Goldberg snarks and flower snarks. In particular, it is shown that flower snarks have a Petersen-coloring but they do not have a strong Petersen-coloring. Furthermore it is proved that possible minimum counterexamples to Jaeger's Petersen-coloring conjecture do not contain a specific subdivision of K3 3.
Keywords: Petersen colorings, strong Petersen colorings, snarks Math. Subj. Class.: 05C15, 05C21, 05C70
1 Introduction
We study finite graphs G with vertex set V(G) and edge set E(G). If we distinguish an initial and a terminal end for every edge e, then we obtain a directed graph. For S C V(G), the set of edges with initial end in S and terminal end in V(G) - S is denoted by w+(S). We write w- (S) = w+(V (G) - S) and (S) = w+(S) U w-(s). If S consists ofasingle vertex v we also write wG(v) instead of wG({v}). Subsets of E(G) of the form wG(S) for S C V(G) are called cocycles of G. If R C E(G), then G[R] denotes the graph with vertex set V (G) and edge set R.
Given graphs G and H, we say that f : E(G) ^ E(H) is a H-coloring of G if it is a proper edge-coloring and for every v G V(G) there exists a v' G V(H) such that f (wG(v)) C wH(v'). That is, adjacent edges in G are mapped to adjacent edges in H. If H is the Petersen graph, we say that G has a Petersen-coloring.
E-mail addresses: jonas.hagglund@math.umu.se (Jonas Hagglund), eckhard.steffen@uni-paderborn.de (Eckhard Steffen)
Abstract
©® This work is licensed under http://creativecommons.Org/licenses/by/3.0/
161
ArsMath. Contemp. 7 (2014) 123-140
Jaeger [6] studied nowhere-zero flow problems on graphs where the set of flow values are certain subsets of some Abelian group. He showed that a number of problems in graph theory such as the cycle double cover conjecture [9, 12] and Fulkerson's conjecture [2] (i.e. that every bridgeless cubic graph has six perfect matchings such that every edge is in precisely two of them) can be formulated in terms of such flows. He posed the following conjecture which would imply both previously mentioned conjectures, and many others, see [8].
Conjecture 1.1 (Petersen Coloring Conjecture [6]). Every bridgeless cubic graph has a Petersen-coloring.
In [5] an even more specific notion is introduced. Associate to G a directed graph dG with vertex set V(dG) = V(G) U E(G), and to every edge e = xy in G correspond two directed edges ex and ey with initial end e and terminal ends x and y, respectively. We say ex is opposite to ey and vice versa. Let G and G' be two graphs. A mapping ^ from E(dG) to E(dG') is compatible, if for any two opposite edges ei and e2 in dG, ^>(ei) and ^(e2) are opposite edges in dG'.
For a cubic graph G the set of triples of edges of dG of the form wdG(v) is denoted by T + (dG), where v is a trivalent vertex in dG. T-(dG) is the set of triples of the form {e-, e-,e-} where {e1, e2, e3} G T+(dG) and e- is opposite to ej.
Let G and G' be two cubic graphs. A dG'-coloring of dG is a compatible mapping Y from E(dG) to E(dG') which maps every triple of T +(dG) to a triple of T +(dG') U T- (dG'). For the particular case when dG has a dG'-coloring and G' is the Petersen graph, we say that G is strongly Petersen-colorable.
Clearly, strongly Petersen-colorable graphs satisfy the Petersen-coloring conjecture and hence Fulkerson's and the cycle double cover conjecture as well. Jaeger [5] noticed that moreover these graphs also satisfy Tutte's 5-flow- and the orientable cycle double cover conjecture.
All these conjectures are trivially true for 3-edge-colorable cubic graphs. Hence we focus on bridgeless cubic graphs, which are not 3-edge-colorable; so called snarks. Snarks are of major interest in graph theory since they are potential counterexamples to many hard conjectures. Brinkmann et al. [1] generated all snarks with at most 36 vertices and they disproved a couple of conjectures concerning these graphs. The paper also gives an overview on conjectures which are related to snarks. In [11] it is shown that cubic graphs with high cyclic connectivity have a nowhere-zero 5-flow. This result can also be considered as a first approximation to a conjecture of Jaeger and Swart [7] who conjectured that every cyclically 7-edge connected cubic graph has a nowhere-zero 4-flow.
The paper is organized as follows. The next section delivers Jaeger's characterizations of Petersen-colorable and strongly Petersen-colorable graphs, [5]. We show that type 1 Blanusa snarks have a strong Petersen-coloring while flower snarks do not have such a coloring. We study the structure of a minimum counterexample to the Petersen-coloring conjecture and finally we show that the flower-, the Goldberg-, and all Blanusa snarks have a Petersen-coloring.
2 Normal 5-edge-colorings
Let G be a cubic graph and ^ : E(G) ^ {1,2,3,4, 5} be a proper 5-edge-coloring. An edge e = xy in G is poor if |^>(w(x)) U ^(w(y))| = 3 and it is rich if |^>(w(x)) U ^(w(y))| =
J. Hagglund and E. Steffen: Petersen-colorings and some families ofsnarks	163
5. If every edge in G is either rich or poor, then ^ is a normal 5-edge-coloring. Jaeger characterizes Petersen-colorable and strongly Petersen-colorable graphs in terms of normal 5-edge-colorings.
Theorem 2.1. [5] A cubic graph is Petersen-colorable if and only if it has a normal 5-edge-coloring.
Theorem 2.2. [5] A cubic graph is strongly Petersen-colorable if and only if it has a normal 5-edge-coloring, and the set of poor edges forms a cocycle.
If ^ is a normal 5-edge-coloring of a graph G, such that the set of poor edges forms a cocycle, then we call ^ a strong normal 5-edge-coloring. Jaeger [5] stated that cubic graphs with strong normal 5-edge-coloring do not contain a triangle (cf. Proposition 4.1).
3 Strong Petersen-colorings 3.1 Blanusa snarks
The generalized Blanusa snarks were introduced by Watkins in [13]. Let A be the graph formed by removing two adjacent vertices from the Petersen graph. The generalized Blanusa snarks of type 1 are formed by joining n copies of the graph A as depicted in Figure 1 and one copy of the graph P2.
Figure 1: The generalized Blanusa snark of type 1.
Theorem 3.1. Every generalized Blanusa snark of type 1 with an odd number of A-blocks is strongly Petersen-colorable.
Proof. Let G2n-1 be a Blanusa snark of type 1 formed by blocks Ai,..., A2n+1, P2 and let ^ be the coloring of the even respectively odd blocks as shown in Figure 2. Then it is easy to see that ^ is a normal edge-coloring where the set of poor edges is the set U{u(V(Aj))}2" and hence a cocycle. It now follows from Theorem 2.2 that G2n-1 is strongly Petersen-colorable.	□
3.2 Flower snarks
In this section we will show that flower snarks do not have a strong Petersen-coloring.
Let G be a graph which has a normal 5-edge-coloring. We first study possible partitions of the edge set of C6 (the cycle of length 6) into rich and poor edges. We denote the set of rich edges with R.
164
ArsMath. Contemp. 7 (2014) 123-140
Figure 2: A normal edge-coloring ^ of a generalized Blanusa snark of type 1 where the only poor edges are the diagonal edges between the blocks A\,..., A2n+1.
Lemma 3.2. Let G be a cubic graph that has a strong normal 5-edge-coloring. If C6 is a subgraph of G, then the connected components of C6[E(C6) n R] are either C6 or two paths of length 2 or two isolated edges and two isolated vertices or six isolated vertices.
Proof. Let G be a cubic graph that has a strong normal 5-edge-coloring and that contains C6 as a subgraph. Then the set of poor edges forms a cocycle by Theorem 2.2 and therefore, it partitions V(G) into two sets S and S' such that the following two conditions are satisfied:
C1: If e = vw is a poor edge, then v e S if and only if w G S'. C2: If e = vw is a rich edge, then either v,w G S or v,w G S. Taken into account these two conditions, it is easy to see that the following claim is true.
Claim 3.3. The number of rich (poor) edges in C6 is even.
Figure 3: C6
Let the edges of C6 be labeled as indicated in Figure 3.
Claim 3.4. The rich edges do not induce a path of length 4.
J. Hagglund and E. Steffen: Petersen-colorings and some families ofsnarks	165
Proof. Assume that e^e2,e3,e4 are rich. W.l.o.g. we may assume that ¿(e^ = 1, ¿(/1) = 2, ¿(ee) = 3, ¿(/2) = 4, ¿(e2) = 5. Then ¿(^,¿^,¿(/4)^4) = 5. Hence 5 G {¿(/5), ¿(e5)}. But on the other hand {¿(e5), ¿(/5)} = {1, 3} or = {2,3}, a contradiction.
Claim 3.5. The rich edges do not induce a path of length 3 and an isolated edge in Ce.
Proof. Assume that e1,e2,e3,e5 are rich. W.l.o.g. we may assume that ¿(e1) = 1, ¿(/1) = 2, ¿(ee) = 3, ¿(/2) = 4, ¿(e2) = 5. This implies, that {¿(e4), ¿(/4)} = {1,4} and {¿(e4), ¿(/5)} = {4,5}; hence ¿(e4) = 4. Thus ¿(/5) = 5 = ¿(/4), a contradiction.
Claim 3.6. The rich edges do not induce precisely one path of length 2 in Ce.
Proof. Assume that e1, e2 are rich. W.l.o.g. we may assume that ¿(e1) = 1, ¿(/1) = 2, ¿(ee) = 3, ¿(/2) = 4, ¿(e2) = 5. This implies that 3 G {¿(/5), ¿^4)} and 5 G {¿(e4), ¿(/4)}. On the other hand we have that {¿(e5), ¿(ee), ¿(/e)} = {1,2,3} and hence 5 G {¿(e4)^(/5)}. But then ¿(e4) = 3, ¿(/4) = 5 and therefore 5 G {¿(ee), ¿(/5)}, a contradiction.	□
For the further study we will go a little bit more into the details of possible (strong) normal 5-edge-colorings.
Lemma 3.7. Let G be a cubic graph that has a normal 5-edge-coloring ¿. If Ce is a subgraph of G and all its edges are rich, then E (Ce) is partitioned into three color classes,
say ¿-1(1), ¿-1(2), ¿-1(3), such that e», ej+3 G ¿-1(i),for i =1, 2, 3.
Proof. Clearly, at least three colors appear at the edges of Ce since for otherwise there are two edges of the same color with distance 1, contradicting the fact that all edges are rich. If more than three colors appear at the edges of Ce, then there is a path of length 4,
say e1, e2, e3, e4, whose edges are colored pairwise differently, say ¿(ej) = i. W.l.o.g. we may assume that ¿(/2) = 4 and ¿(/3) = 5. Thus ¿(/4) = 1, and since all edges are rich, it follows that {¿(e5), ¿(/5)} = {2,5}, {¿(ee), ¿(/1)} = {3,5}, and hence {¿(ee), ¿(/e)} = {1, 3} and {¿(e5), ¿(/e)} = {2,4}, a contradiction. It is easy to see that a coloring as stated in the claim exists.	□
Lemma 3.8. Let G be a cubic graph that contains Ce as a subgraph and ¿ be a strong normal 5-edge-coloring. If precisely two edges of Ce are rich, then they receive the same color.
Proof. It follows from Lemma 3.2 that there are two non-isomorphic distributions of the rich edges.
1)	The distance between the rich edges in Ce is 2. Assume that e1, e4 are rich. W.l.o.g. we may assume that ¿(e1) = 1, ¿(/1) = 2, ¿(ee) = 3, ¿(/2) = 4, ¿(e2) = 5. Assume to the contrary ¿(e4) = 1.
Case 1: ¿(e5) = 1. Then it follows that ¿(/3) = 1 and ¿(/4) = 1, contradicting the fact that e4 is rich.
Case 2: ¿(e5) = 1, i.e. ¿(e5) = 2, and hence ¿(/e) = ¿(/5) = 1 and ¿(e4) = 3. But 3 G {¿(e2), ¿(/3)}, a contradiction.
2)	The distance between the rich edges in Ce is 1. Assume that e1, e3 are rich. W.l.o.g. we may assume that ¿(e1) = 1, ¿(/1) = 2, ¿(ee) = 3, ¿(/2) = 4, ¿(e2) = 5. Assume to the contrary ¿(e3) = 1. Then ¿(e3) = 4 and hence 4 G {¿(e5), ¿(/5)}, and therefore
166
ArsMath. Contemp. 7 (2014) 123-140
in any case 4 e {^(e5), 4>(f6),4>(e6)}. But on the other hand {^(e5), ^(f6), ^(e6)} = {1, 2,3 }, a contradiction.	□
Figure 4: CQ
Let CQ be the graph of Figure 4 without the edges f, f3, f4, f6. Our objective is to reduce the number of non-isomorphic partitions of the edge set of CQ into rich and poor edges to the five partitions shown in Figure 5.
Figure 5: Five types of non-isormorphic partitions of E(CQ) into rich and poor edges. (The rich edges are bold.)
Lemma 3.9. Let G be a cubic graph that has a strong normal 5-edge-coloring. If CQ is a subgraph of G and Ep, Er is a partition of the edges of E(CQ) into poor and rich edges, then this partition is isomorphic to one of the types in Figure 5.
Proof. The result follows by case checking along the number r of rich edges in CQ. Let the edges of CQ be labeled as in Figure 4. It contains three C6 - with edge sets {ei, e2,..., e6},
{ei, f2, fo, f5, e5, e6}, and {e2, e3, e4, f5, f0, f2} - which share pairwise a path of length 3.
J. Hagglund and E. Steffen: Petersen-colorings and some families ofsnarks	167
r = 0: We obtain a partition of type A of Figure 5.
r = 1: Then there is a C6 with an odd number of rich edges, contradicting Lemma 3.2. r = 2: By Lemma 3.2 any of the three C6 has either no rich edge or two rich edges, which induce two isolated edges. Now it is easy to see that type B of Figure 5 is the only solution (up to isomorphism).
r = 3: By Lemma 3.2 any of the three C6 has two rich edges, which induce two isolated edges. It is easy to see that types C and D are the only possible solutions.
r = 4: The matching number of Cg is 4. If r = 4 and the four rich edges induce a matching, then there is a C6 that contains an odd number of rich edges, a contradiction. Thus, by Lemma 3.2, we can assume that there is a C6 such that the rich edges induce two paths of length 2. The only realizable partition is of type E of Figure 5 (up to isomorphism). 5 < r < 8: It is easy to see that Lemma 3.2 can not be satisfied for all three C6 of Cg. r = 9: In this case, we obtain a contradiction to Lemma 3.7.	□
The following lemma easily follows from Lemma 3.8.
Lemma 3.10. Let G be a cubic graph that has a strong normal 5-edge-coloring. If Cg is a subgraph of G and the edges of E(Cg) are partitioned into poor and rich edges as shown in Figure 5 B, C or D, then the three rich edges receive the same color.
The flower snarks are invented by Isaacs [4]. They are cyclically 6-edge connected and have girth 6, if k > 3. For k > 1, the flower snark J2k+1 has vertex set V(J2k+1) = {cm, bi, ci, di|i = 0,1,..., 2k} and edge set E( J2k+i) = {Mi, biQ, bidi; ajai+i; Cjdi+i; dici+i\i = 0,1..., 2k} (indices are added modulo 2k + 1).
Theorem 3.11. For every k > 1, the flower snark J2k+1 is not strongly Petersen-colorable.
Figure 6: Substructure of J2k+1
Proof. We show that the flower snarks do not have a strong normal 5-edge-coloring. Then the result follows with Theorem 2.2. Assume to the contrary that J2k+1 has a strong normal 5-edge-coloring Let Cg be the graph as indicated in Figure 4. The flower snark J2k+1 can be considered as the union of 2k +1 copies D0,..., D2k of Cg, where Di and Di+1 share precisely the subgraph which is induced by one vertex of degree 3 and its neighbors (indices are added modulo 2k + 1); see Figure 6. By Lemma 3.9, the five partitions of the edges of C6g shown in Figure 5 are the only non-isomorphic types of possible partitions of the edges of C6g into rich and poor edges.
1) There is i G {0 ... 2k} such that Di is of type E. Since Di shares with Di+1 a vertex of degree 3 with its three incident edges, it follows that Di+1 is of type E as well.
168
ArsMath. Contemp. 7 (2014) 123-140
Hence all Di are of type E and therefore all edges of the inner cycle of length 2k + 1 are poor, contradicting our assumption, that J2k+1 has a strong normal 5-edge-coloring. Thus all Di are not of type E.
2)	There is i e {0... 2k} such that Di is of type D. Then Di+1 can be of any other type different from E. We may assume that the edge bici is rich. Hence ci-1di and ai-1ai are rich, too. All the other edges of Di are poor. If Di+1 is of type C or D, then it follows, that two different rich edges, one of Di and one of Di+1 are adjacent. By Lemma 3.10, they all have the same color, contradicting the fact that ^ is a coloring. Thus Di+1 is of type B. On the other hand, Di-1 shares with Di the vertex 6i-1 of degree 3 which is incident to three poor edges. As above, it follows that Di-1 cannot be of type D; thus it is of type A. Since the number of the Di is odd it follows that the types A, B, C and D cannot combined to get a coloring of J2k+1. Thus all Di are not of type D.
3)	There is i e {0... 2k} such that Di is of type A. Since Di shares with Di+1 a vertex of degree 3 with its three incident edges, it follows that Di+1 is of type A as well. Not all Dj can be of type A since then J2k+1 has no rich edges and therefore it is 3-edge-colorable, a contradiction. Thus all Di are of type B or C.
4)	There is i e {0... 2k} such that Di is of type B or C. It follows that Di+1 is of type B or C. It turns out, that in any case the two rich edges which are adjacent to the trivalent vertices bi and bi+1 are of the form bici, bi+1di+1 or bidi, bi+1Q+1. This implies that eventually two edges bj cj and bj dj are rich, contradicting the fact that every Di is of type B or C.
Since the five types of Figure 5 are the only possible strong normal 5-edge-colorings of Cg and no combination of them yields a strong normal 5-edge-coloring of J2 k+1, it follows with Theorem 2.2 that J2k+1 has no strong Petersen-coloring.	□
4 Structure of a possible minimum counterexample to the Petersen-coloring conjecture
Jaeger [6] showed that a possible minimum counterexample to the Petersen-coloring conjecture must be cyclically 4-edge connected snark.
If G contains a triangle, then let G- be the graph obtained from G by contracting the triangle to a single vertex. Clearly, every normal 5-edge-coloring of G- can be extended to one of G. On the hand, if a cubic graph G has a normal 5-edge-coloring then this coloring can be extended to any graph which is obtained from G by expanding a vertex to a triangle. The following proposition is a reformulation of Proposition 15 in [5].
Lemma 4.1. Let ^ be a normal 5-edge-coloring of a bridgeless cubic graph G. If there is an edge e which is contained in a triangle, then e is poor.
Proof. Let e1 = v1v2, e2 = v2v3, e3 = v3v1 be the edges of a triangle T in G and let fi be the edge which is incident to vi and not an edge of T. Assume that e1 is rich, then |^(w(v1))) U ^(w(v2))| = 5 and hence e1, e2, e3, f1, f2 and f3 have to receive pairwise different colors; contradicting the fact that ^ is a 5-edge-coloring.	□
Consider K3,3 with partition sets {u, v, w} and {v1, v2, v3}. Let be the graph obtained from K3,3 by subdividing the edges uvi and wvi by vertices ui and wi, respectively. Graph K|,3 is shown in Figure 7.
J. Hagglund and E. Steffen: Petersen-colorings and some families ofsnarks
169
Figure 7:
It is easy to see that the statements of this section are also true if we consider Fulkerson-colorings (i.e. a cover with six perfect matchings such that every edge is contained in precisely two of them) instead of Petersen-colorings.
Theorem 4.2. If G is a minimum counterexample to the Petersen-coloring conjecture (or to the Fulkerson conjecture), then it does not contain K**3 as a subgraph.
Proof. Let ^ be a normal 5-edge-coloring of G, and assume that K|,3 is a subgraph of G. Remove the vertices u and w and add edges «¿w.j, for i = 1, 2, 3, to obtain a cubic graph G'. Since G is cyclically 4-edge connected it follows that G' is bridgeless. Thus G' has a normal 5-edge-coloring by induction hypothesis. Since «¿, vj, wj span a triangle in G' (i = 1, 2,3), it follows by Lemma 4.1 that edge ujwj receives the same color as vvj. Thus is extendable to a normal 5-edge-coloring of G, a contradiction. The statement follows with Theorem 2.1. The proof for the Fulkerson conjecture is similar.	□
This also yields a method to generated cubic graphs with normal 5-edge-colorings from smaller ones (with normal 5-edge-coloring). Let v be a vertex of a cubic graph with normal 5-edge-coloring and let wi, w2, w3 be the neighbors of v. Expand wj to a triangles Tj with vertex set {wj,1, wj,2, wj,3} such that v, wj,1 are incident, to obtain a graph G1. Then ^ can be extended to a normal 5-edge-coloring on G1. By Lemma 4.1 it follows that ^1(vwj1) = ^1(wj,2wj 3). Hence edges wj 2wj 3 can be removed and two vertices can be added so that we obtain a K3* 3 as a subgraph and a normal 5-edge-coloring of the new graph.
We will use this fact, to prove Conjecture 1.1 for flower snarks.
5 Petersen-colorings for some families of snarks 5.1 Flower snarks
If a cubic graph G contains a K3,3 and we reduce it to a smaller graph G' as in the proof of Theorem 4.2, then G' contains three triangles. If we contract these three triangles to single vertices we obtain a new cubic graph G* that has 8 vertices less than G. Let us say that G is K3,3-reducible to G*. Theorem 4.2 can be reformulated as follows:
170
ArsMath. Contemp. 7 (2014) 123-140
Theorem 5.1. Let G be a cubic graph that is K^^-reducible to a graph H. If H has a Petersen-coloring, then G has a Petersen-coloring.
The following lemma is a simple consequence of Lemma 4.2 of [10].
Lemma 5.2. For k > 1, the flower snark J2k+3 is K^3-reducible to J2k+1.
Since J3 can be reduced to the Petersen graph by contracting the triangle to a single vertex, Theorem 5.1 and Lemma 5.2 imply the following theorem.
Theorem 5.3. For all k > 1, the flower snark J2k+1 has a Petersen-coloring.
5.2 Goldberg snarks
Let k > 5 be a odd integer. The Goldberg snark [3] Gk is formed from k copies B1,.. of the graph B in Figure 8 and the edges {a,jai+1, Cj6i+1, e.jdi+1} for each i € {1,2,.. where indices are added modulo k.
■ , Bk ., k}
Figure 8: A block B in the Goldberg snark.
Theorem 5.4. Every Goldberg snark Gk, where k > 5 is odd, has a Petersen-coloring.
Proof. Let Gk be a Goldberg snark. Then Gk can be constructed from one 3-block (see Figure 10) and k-3 2-blocks (see Figure 9). Using the normal 5-edge-colorings provided in Figure 9 and 10 it is easy to see that it will give a normal 5-edge-coloring of Gk. □
5.3 Blanusa snarks
Let G be a Blanusa snark of type 1 as defined in Section 3.1. If we color the blocks A1,..., Ar-1 as in figure 11 and Ar and C1 as in figure 12 and 13, it is easy to see that we have a normal edge coloring of all such graphs.
The generalized Blanusa snarks of type 2 are formed by joining r copies of A and one copy of C2 (see Figure 14). Once again it is straightforward to see that all such graphs has normal edges colorings by coloring A1,..., Ar-2 as in Figure 11, Ar-1 as in Figure 13 and finally C2 as in Figure 14.
From this we get the following theorem.
Theorem 5.5. All generalized Blanusa snarks of type 1 and 2 have Petersen-colorings.
J. Hagglund and E. Steffen: Petersen-colorings and some families ofsnarks	171
4	4
Figure 9: A 2-block in the Goldberg snark with a normal 5-edge-coloring.
Figure 10: A 3-block in the Goldberg snark with a normal 5-edge-coloring.
Figure 11: Block A in the generalized Blanusa snark.
172
Ars Math. Contemp. 7 (2Û14) 161-173
Figure 12: Block Ar in the generalized Blanuša snark.
Figure 13: Block P2 in the generalized Blanuša snark.
Figure 14: Block C2 in the generalized Blanuša snark.
J. Hagglund and E. Steffen: Petersen-colorings and some families ofsnarks	173
References
[1]	G. Brinkmann, J. Goedgebeur, J. Hagglund and K. Markstrom, Generation and properties of snarks (2012), arXiv:120 6.6690v1.
[2]	D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Math. Programming 1 (1971), 168-194.
[3]	M. K. Goldberg, Construction of class 2 graphs with maximum vertex degree 3, J. Combin. Theory Ser. B 31 (1981), 282-291, doi:10.1016/00 95-8956(81)90030-7.
[4]	R. Isaacs, Infinite families of nontrivial trivalent graphs which are not Tait colorable, Amer. Math Monthly 82 (1975), 221-239.
[5]	F. Jaeger, On five-edge-colorings of cubic graphs and nowhere-zero flow problems, Ars Combin. 20 (1985), 229-244.
[6]	F. Jaeger, Nowhere-zero flow problems, in: Selected topics in graph theory, 3, Academic Press, San Diego, CA, pp. 71-95, 1988.
[7]	F. Jaeger and T. Swart, Conjecture 1 and 2, in: M. Deza and I. G. Rosenberg (eds.), Combinatorics 79, volume 9, 1980.
[8]	D. Krdl, E. Mdcajovd, O. Pangrdc, A. Raspaud, J.-S. Sereni and M. Skoviera, Projective, affine, and abelian colorings of cubic graphs, European J. Combin. 30 (2009), 53-69, doi: 10.1016/j.ejc.2007.11.029.
[9]	P. D. Seymour, Sums of circuits, in: Graph theory and related topics (Proc. Conf., Univ. Waterloo, Waterloo, Ont., 1977), Academic Press, New York, 1979, pp. 341-355.
[10]	E. Steffen, Classifications and characterizations of snarks, Discrete Math. 188 (1998), 183-203, doi:10.1016/S0012-365X(97)00255-0.
[11]	E. Steffen, Tutte's 5-flow conjecture for highly cyclically connected cubic graphs, Discrete Math. 310 (2010), 385-389.
[12]	G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc. 8 (1973), 367-387.
[13]	J. J. Watkins, On the construction of snarks, Ars Combin. 16 (1983), 111-124.