Also available at http://amc.imfm.si
ISSN 1855-3966 (printed ed.), ISSN 1855-3974 (electronic ed.)
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 169–184
Relating Embedding and Coloring Properties of
Snarks
Bojan Mohar ∗ †
Department of Mathematics, Simon Fraser University, Burnaby, BC, V5A 1S6, Canada
Eckhard Steffen
Paderborn Institute for Advanced Studies in Computer Science and Engineering
Universität Paderborn, Warburger Straße, D-33098 Germany
Andrej Vodopivec ‡
Faculty of Information and Computer Science, University of Ljubljana
Tržaška 25, SI-1000 Ljubljana, Slovenia
Received 29 November 2007, accepted 9 December 2008, published online 27 December 2008
Abstract
In 1969, Grünbaum conjectured that snarks do not have polyhedral embeddings into ori-
entable surfaces. To describe the deviation from polyhedrality, we define the defect of a graph
and use it to study embeddings of superpositions of cubic graphs into orientable surfaces. Su-
perposition was introduced in [4] to construct snarks with arbitrary large girth. It is shown
that snarks constructed in [4] do not have polyhedral embeddings into orientable surfaces.
For each k ≥ 2 we construct infinitely many snarks with defect precisely k. We then relate
the defect with the resistance r(G) of a cubic graph G which is the size of a minimum color
class of a 4-edge-coloring of G. These results are then extended to deal with some weaker
versions of the Grünbaum Conjecture.
Keywords: Graph embedding, resistance, snark, superposition.
Math. Subj. Class.: 05C10, 05C15
∗Supported in part by an NSERC Discovery Grant, by an NSERC Accelerator Supplement, by the CRC Program,
and by the Ministry of Higher Education, Science and Technology of Slovenia, Research Program P1-0297.
†On leave from IMFM & FMF, Department of Mathematics, University of Ljubljana, SI-1000 Ljubljana, Slove-
nia.
‡Supported in part by the Ministry of Higher Education, Science and Technology of Slovenia, Research Program
P1-0297.
E-mail addresses: mohar@sfu.ca (Bojan Mohar), es@upb.de (Eckhard Steffen), andrej.vodopivec@fri.uni-lj.si
(Andrej Vodopivec)
Copyright c© 2008 DMFA – založništvo
170 Ars Mathematica Contemporanea 1 (2008) 169–184
1 Introduction
In this paper we study 2-cell embeddings of cubic graphs into closed orientable surfaces.
All graphs will be simple and without loops. We follow the notation of [5]. A (orientable)
combinatorial embedding Π of a graph G is given by a rotation system and two embeddings
are (combinatorially) equivalent if they define the same collection of facial walks. To describe
an embedding it is sufficient to list all facial walks. An embedding given by a collection F of
facial walks is orientable if we can orient walks in F so that each edge appears twice along
walks in F , once in each direction. Any such orientation is called a consistent orientation.
Unless stated otherwise, all embeddings considered are orientable.
An embedding of a graph is polyhedral if all facial walks are cycles and any two of them
are either disjoint, intersect in one vertex or intersect in one edge. Therefore, an embedding
of a cubic graph is polyhedral if all facial walks are cycles and any two of them are either
disjoint or they intersect in precisely one edge.
The study of polyhedral embeddings of cubic graphs is motivated by the following con-
jecture of Grünbaum [3].
Conjecture 1 (Grünbaum Conjecture). If a cubic graph admits a polyhedral embedding into
an orientable surface, then it is 3-edge-colorable.
Grünbaum proposed this conjecture in 1969 [3] as a generalization of the Four Color
Theorem, which was not yet proved at that time. At present it is known that it is true for the
plane (follows from the Four Color Theorem). Recently, Kochol announced that he found
counterexamples to the conjecture on surfaces with genus at least five. The conjecture is still
open for other surfaces.
For each orientable surface S we can state the Grünbaum Conjecture for S.
Conjecture 2 (Grünbaum Conjecture for S). If a cubic graph admits a polyhedral embedding
into the orientable surface S, then it is 3-edge-colorable.
Let Π be an embedding of a 3-connected cubic graphG into a surface S. Consider its dual
multigraph G∗, and observe that the embedding is polyhedral if and only if G∗ is a simple
graph. Let w be the length of a shortest cycle in G∗ which is non-contractible in S. Then w
is called the face-width of the embedding Π. It is easy to see that Π is polyhedral if and only
if the face-width is at least 3 (and G is 3-connected). See [5] for more details.
Robertson and Mohar proposed a weakening of Grünbaum’s Conjecture, where the as-
sumption on the face-width is strengthened (see [5]).
Conjecture 3 (Grünbaum, Mohar, Robertson). There exists an integer k such that the follow-
ing holds. If a cubic graph admits an embedding into an orientable surface with face-width
at least k, then it is 3-edge-colorable.
In [2] it is also conjectured that 3-connected cubic graphs with embeddings of face-width
at least 4 are 3-edge-colorable. However, it is not even known if any lower bound on the
face-width guarantees 3-edge-colorability for any non-simply connected fixed surface.
By a theorem of Vizing, simple cubic graphs are either 3- or 4-edge-colorable. Cycli-
cally 4-edge-connected cubic graphs with girth at least 4 which are not 3-edge-colorable are
called snarks. Grünbaum’s conjecture is equivalent to the statement that snarks do not admit
polyhedral embeddings into orientable surfaces.
Grünbaum’s conjecture has been verified for many families of snarks since its formulation
in 1969. Szekeres [10] proved it for flower snarks J2k+1 and the Szekeres graph, in [6] it was
B. Mohar et al.: Relating Embedding and Coloring Properties of Snarks 171
proved for Goldberg snarksG2k+1. However the proofs do not rely on the coloring properties
of graphs. It can be shown that no graph Jn or Gn, n ≥ 3, admits an orientable polyhedral
embedding and that the graphs Jn neither have polyhedral embeddings into non-orientable
surfaces [6].
Let Π be an embedding of a cubic graph G and let F = {W1, . . . ,Wk} be the collection
of facial walks of Π. For a walk Wi ∈ F we define the defect d(Wi) of Wi to be the number
of edges which appear twice along Wi. For two facial walks Wi,Wj ∈ F , i 6= j, we define
the defect d(Wi,Wj) = max{0, |E(Wi) ∩ E(Wj)| − 1}. The defect of the embedding Π is
defined as
d(G,Π) = d(Π) =
k∑
i=1
d(Wi) +
∑
1≤i<j≤k
d(Wi,Wj).
and the defect of the graph G is defined as
d(G) = min{d(G,Π) | Π is an orientable embedding of G}.
In an embedding Π of G, a pair of facial walks is a bad pair if they have more than one edge
in common. An edge e is a bad edge if it appears twice along a facial cycle of Π or if there
is another edge f such that e and f both appear on two facial walks Wi and Wj . In the latter
case we call the edges e and f a bad pair of edges.
It is clear from the definition of the defect that a graph G admits a polyhedral embedding
into an orientable surface if and only if d(G) = 0. The Grünbaum Conjecture is therefore
equivalent to the statement that for any snark G the defect d(G) is at least 1. We give a
stronger connection in Section 4.
The defect d(G,Π) can also be expressed as follows.
Lemma 4. If G is a 3-connected Π-embedded cubic graph, then d(G,Π) equals the min-
imum cardinality of an edge set F ⊆ E(G) with the property that every non-contractible
cycle C∗ of length 1 or 2 in the dual graph G∗ intersects at least one edge in F .
Proof. If F ⊆ E(G) has the property that every non-contractible cycle C∗ in the dual graph
G∗ intersects at least one edge in F , then we say that F is a blocking set. It is clear that
every blocking set has to contain all edges which appear twice in some facial walk. Namely,
since G is 2-connected, every such edge gives rise to a non-contractible loop in the dual G∗.
Similarly, 3-connectivity implies that every pair of edges shared by two facial walks Wi,Wj
gives rise to a non-contractible 2-cycle in G∗. Therefore, if |E(Wi) ∩ E(Wj)| ≥ 2, every
blocking set contains all but at most one of the edges in E(Wi) ∩ E(Wj). This proves that
|F | ≥ d(Π). The converse inequality holds for the set F in which we put all the edges shown
above to be necessarily included. This completes the proof.
Embeddings of snarks and in particular snarks obtained as dot products have been studied
in [11, 8, 7]. The genus of the Petersen graph is 1 and the genera of the two Blanuša snarks,
which are the two possible dot products of the Petersen graph, are 1 and 2. Using a computer
program which goes over all possible rotation systems we also computed the defects of some
small snarks. In particular for the Petersen graph P and the Blanuša graph B1 of genus 1 we
have the following lemma.
Lemma 5. Let P be the Petersen graph andB1 the Blanuša snark of genus 1. Then d(P ) = 5
and d(B1) = 3.
172 Ars Mathematica Contemporanea 1 (2008) 169–184
Figure 1: An embedding of the Petersen graph in the torus.
Figure 1 shows an embedding of the Petersen graph in the torus with defect 5 and Figure
2 shows the graph B1 embedded in the torus with defect 3.
Further, using a computer, we found that the smallest possible defect among snarks with
up to 28 vertices is 2. We describe an orientable embedding of a snarkG26 on 26 vertices with
defect 2. The graph G26 has vertices labeled with integers from 1 to 26 and the embedding
has the following facial cycles:
Face 1: 1 2 5 9 4
Face 2: 2 1 3 8 14 18 12 6
Face 3: 3 1 4 10 7
Face 4: 5 2 6 11 13 8 3 7
Face 5: 5 7 10 16 25 26 23 15 9
Face 6: 4 9 15 22 24 16 10
Face 7: 11 6 12 19 17
Face 8: 8 13 20 21 14
Face 9: 13 11 17 24 22 20
Face 10: 12 18 26 25 19
Face 11: 18 14 21 23 26
Face 12: 17 19 25 16 24
Face 13: 21 20 22 15 23
The snark G26 has two orientable embeddings with defect 2. There are two snarks with 28
vertices with defect 2. All other snarks with at most 28 vertices have defect at least 3.
2 Superposition
We give a short description of superposition of graphs. For the details see [4]. A multipole
M = (V,E, S) consists of a set of vertices V , edges E and semiedges S. A semiedge s is
incident with one vertex v and denoted by s = (v). We assume that the degrees of vertices
in a multipole are all 3 (the degree of a vertex v in a multipole is the number of edges and
semiedges incident with v). A (k1, . . . , kn)-pole is a multipole (V,E, S) with a partition of
semiedges into sets S = S1 ∪ · · · ∪ Sn with |Si| = ki, i = 1, . . . , n. The sets S1, . . . , Sn
are called the connectors of the multipole. A (k1, k2)- pole is called a superedge and a
B. Mohar et al.: Relating Embedding and Coloring Properties of Snarks 173
(k1, k2, k3)-pole is called a supervertex. A (1, 1, 1)-pole consisting of a single vertex v and
three semiedges incident with v is called a trivial supervertex.
Let G be a snark. We remove two non-adjacent vertices v and u from G and replace all
edges vxi incident with v with semiedges (xi), i = 1, 2, 3, and all edges uyi with semiedges
(yi), i = 1, 2, 3. We define S1 = {(x1), (x2), (x3)} and S2 = {(y1), (y2), (y3)} to obtain
a (3, 3)-multipole with connectors S1 and S2. We say that we have obtained a proper su-
peredge by removing vertices v and u from G. An empty multipole will be considered as a
special (1, 1)-multipole and a proper superedge. An empty multipole is also called a trivial
superedge. For a broader definition of a proper superedge see [4].
Let G = (V,E) be a cubic graph. To each vertex v ∈ V we assign a supervertex S(v)
and additionally to each edge incident to v we assign one of the connectors of S(v). To each
edge xy ∈ E we assign a (proper) superedge E(x, y). If E(x, y) is not an empty multipole
we assign one of the connectors of E(x, y) to x and the other to y.
Assume that for each edge e = xy ∈ E the following holds. If E(x, y) is an empty
multipole then the connectors assigned to e in supervertices S(x) and S(y) have cardinal-
ity 1. Otherwise the connector assigned to the edge e in the supervertex S(x) has the same
cardinality as the connector assigned to x in the superedge E(x, y) and the same holds for y.
We can then construct a new graph as follows. If the superedge assigned to e = xy is an
empty multipole, then we remove the semiedge (v) in the connector of S(x) assigned to e and
the semiedge (u) in the connector of S(y) assigned to e and add an edge uv. Otherwise we
have semiedges {(u1), (u2), (u3)} in the connector of S(x) and semiedges {(x1), (x2), (x3)}
in the connector of e assigned to x. We remove them, add the edges {u1x1, u2x2, u3x3} and
do the same for the vertex y. By repeating the procedure for all edges e ∈ E we get a cubic
graph G′ called a superposition of G. If we have assigned proper superedges to all edges,
then the graph G′ is called a proper superposition of G.
The following result is proved in [4]:
Theorem 6. A proper superposition of a snark is a snark.
Superposition is a powerful tool used to construct new snarks from smaller snarks which
generalizes many previously known constructions. This construction was used to obtain
snarks with arbitrary large girth. In Section 5 we show that the snarks with high girth ob-
tained by Kochol in [4] do not have orientable polyhedral embeddings.
3 Defect of a graph and the Grünbaum Conjecture
Let M = (V,E, S) be a multipole. A combinatorial embedding of M is an assignment
of rotations to vertices V . As with combinatorial embeddings of graphs, we can define the
collection of facial walks F , which consists of closed walks and walks which start and end
with semiedges of a connector. Again we can describe the embedding of M by specifying F .
If in the definition of the defect we replace graphs with multipoles, we get the definition of a
defect of a multipole.
Suppose we have an orientable embedding of a superedge M = (V,E, S1 ∪ S2). Let
the connectors be S1 = {(u1), (u2), (u3)} and S2 = {(v1), (v2), (v3)}. Suppose that in
the consistent orientation of facial walks we have walks W1 = u1P1v1, U1 = u2R1u1,
U2 = u3R2u2, W2 = v3P2u3, V1 = v1Q1v2 and V2 = v2Q2v3. Suppose further that the
walks P1 and P2 are disjoint. An embedding as described is called a nice embedding of a
superedge.
174 Ars Mathematica Contemporanea 1 (2008) 169–184
x
y
Figure 2: The Blanuša snark embedded in the torus with defect 3.
11 22
33
44 55
6
7
Figure 3: Supervertices used for replacing edges.
Take the Blanuša snarkB1 embedded in the torus and remove vertices x and y (see Figure
2) to obtain the proper Blanuša superedge B′1. Note that the embedding of B1 in the torus
induces a nice embedding of B′1 with defect 1. Using a computer program, which goes over
all possible rotations of vertices, we have proved the following result.
Lemma 7. The Blanuša superedge B′1 has defect 1.
We now describe what we mean by replacing an edge in an embedded graph with a nicely
embedded superedge. Suppose Π is an embedding of G and e = xy ∈ E(G) is an edge.
Denote the neighbors of x with {y, x1, x2} and the neighbors of y with {x, y1, y2} so that in
the embedding Π there are facial walks C1 = ∗x1xyy1∗, C2 = ∗y1yy2∗, C3 = ∗y2yxx2∗
and C4 = ∗x2xx1∗.
We will use the (1,1,3)-supervertex V from the left hand side of Figure 3 where the con-
nectors are {(1)}, {(5)} and {(2), (3), (4)}. To vertices x and y we assign V(x) and V(y),
both copies of V , to e we assign the nicely embedded superedge (with the notation defined at
the beginning of this section) and to all other vertices and edges we assign trivial superver-
tices and superedges. We denote the vertices in V(y) with 1′, 2′, . . . to distinguish them from
vertices in V(x). In V(x) we assign connectors {(1)}, {(5)}, {(2), (3), (4)} to xx1, xx2, e
and in V(x) we assign connectors {(1′)}, {(5′)}, {(2′), (3′), (4′)} to yy1, yy2, e. In the su-
perposition we add the edges 2u1, 3u2, 4u3 and v12′, v23′, v34′.
This superposition has an induced embedding defined by facial walks F defined as fol-
lows. Take all facial walks of Π which do not contain vertices x and y and modify the facial
B. Mohar et al.: Relating Embedding and Coloring Properties of Snarks 175
walks Ci, i = 1, 2, 3, 4, to get walks C ′i, i = 1, 2, 3, 4, as follows: C
′
1 = ∗x112u1P1v12′
1′y1∗, C ′2 = ∗y11′5′y2∗, C ′3 = ∗y25′4′v3P2u345x2∗ and C ′4 = ∗x251x1∗. Add walks
543215 and 1′2′3′4′5′1′. Add all closed walks in the embedding of the superedge M . Add
walks 23u2R1u12, 34u3R2u23, 3′2′v1Q1v23′ and 4′3′v2Q2v34′. We have described an ori-
entable embedding of a graph G′. If in the embedding Π the cycles C1 and C3 are distinct
then the bad edges in the induced embedding of G′ are the bad edges of Π minus possibly e
and the bad edges in the embedding of the superedge M .
Using the (3, 1, 3)-supervertex from Figure 3 we can similarly replace all edges on a facial
cycle C in G. Again the bad edges in the induced embedding of the superposition are bad
edges in the original graph minus possibly the edges of C and the bad edges in superedges.
Lemma 8. The following statements are equivalent:
(1) The Grünbaum Conjecture is true.
(2) All snarks have defect at least 2.
(3) All nicely embedded proper superedges have defect at least 1.
Proof. First we prove that (1) is equivalent to (3).
If the Grünbaum Conjecture is false, then there exists an embedding of a snark with defect
0. If we remove two non-adjacent vertices from one facial cycle in the embedding we get a
nicely embedded superedge with an induced embedding of defect 0.
Suppose we have a nicely embedded superedge with defect 0. Take the embedding of P
in the torus from Figure 1 and replace each edge along the unique 9-cycle with the nicely
embedded proper superedge to get a snark with defect 0.
It is clear that (2) implies (1). The Grünbaum Conjecture implies that snarks have defect
at least 1. We show that (3) implies that there is no snark with defect precisely 1, which
completes the proof.
Suppose Π is an embedding of a snarkGwith defect 1. First we show that all facial walks
are cycles and that there are two facial cycles C and D which have two edges e = xy and
f = uv in common and that e and f are at distance at least 2 along C and D.
If there is a vertex v in G which appears twice along a facial walk W , then there is an
edge incident with v which appears twice alongW and contributes 1 to the defect of Π. There
is another facial walk which contains v and it intersects W in at least two edges incident with
v. So the defect of Π is at least 2, which shows that all facial walks are cycles.
There are two facial cycles C and D which intersect at two edges e and f . Suppose that
e and f are at distance at most 2 on C. Edges e and f can not be adjacent since in this case
C and D could not be facial cycles in an embedding of G. If they are at distance 1 on C,
assume y and u are adjacent and there are vertices x1 6= x, u and v1 6= y, v such that x1 is
adjacent to y and v1 is adjacent to u. The cycle C contains the path xyuv and the cycle D
contains paths x1yx and vuv1. There is another facial cycle which contains the path v1uyx1
and we get that the defect of the embedding is more than 1.
Now we can choose two vertices w and z on C which are not incident with e or f and w
and z separate e and f on C. Since the defect is 1, the vertices w and z are not on the cycle
D. Remove the vertices w and z from G to obtain a superedge. This is a nicely embedded
superedge with defect 0.
Theorem 9. For each k ≥ 2 there exist infinitely many snarks with defect precisely k. For
each k ≥ 1 there exist infinitely many nicely embedded superedges with defect precisely k.
176 Ars Mathematica Contemporanea 1 (2008) 169–184
Proof. Suppose we have an embedding Π of a snarkG with defect k in which all facial walks
are cycles and there are k bad edges which form an independent set. Let B′1 be the nicely
embedded superedge obtained from the Blanuša snark by removing vertices x and y. Replace
each bad edge in G by B′1 to obtain an embedded snark G
′. By the construction we see that
the defect of G′ is at most k. By Lemma 7 each superedge contributed at least 1 to the defect
of G′, so we get that the defect of G′ is precisely k.
Suppose that inG we can choose k+1 edges such that k of them are bad and one of them
is good and they form an independent set of edges. If we replace each edge with B′1 we get a
snark with the defect precisely k + 1.
Note that if we take the snark G26 with the embedding described in the Introduction we
can perform both operations. Also it is easy to see that after we have performed one operation,
the embedding of the superposition is such that allows us to perform both operations again.
Thus for any k ≥ 3 we can generate infinitely many snarks with defect precisely k.
Let M be a nicely embedded superedge such that all semiedges are good. Then we can
perform the above operations on M to obtain a nicely embedded superedge M ′ such that all
semiedges of M ′ are good. Thus starting with the nice embedding of B′1 we can for each
k ≥ 1 construct infinitely many nicely embedded proper superedges with defect precisely
k.
Suppose G is a cubic graph and let c : E(G) → {1, 2, 3, 4} be an edge-coloring of G.
A coloring c is minimum if the number of edges colored with color 4 is minimum possible
among all edge-colorings of G with at most four colors. The number of edges colored with
color 4 in a minimum coloring is called the resistance, r(G), of G. It is easy to see that a
cubic graph is not 3-edge-colorable if and only if the resistance of G is at least 2, cf. [9].
Suppose Π is an orientable embedding of a cubic graph G. A vertex is called a bad
vertex if in the embedding Π it appears three times along a facial walk. Denote the number
of bad vertices in the embedding Π with dV (Π). We define the modified defect d′(Π) of the
embedding Π with
d′(Π) = d(Π) + 2dV (Π).
and the modified defect of the graph G with
d′(G) = min{d′(Π) | Π an orientable embedding of G}.
Note that d(G) = 0 if and only if d′(G) = 0.
Assume that in the embedding Π of G the vertex v appears three times along a facial
walk F . This implies that the edges, incident with v, each appear twice along a facial walk
F , which contributes 3 to the defect of Π. Suppose that v′ is adjacent to v. The facial
walk which contains edges incident with v and distinct from vv′ intersects F twice at edges
incident with v′. For each vertex adjacent to v we get a contribution 1 to the defect of Π. All
together we have d(Π) ≥ 6dV (Π).
Obviously for each graph G we have d′(G) ≥ d(G) and the Grünbaum Conjecture is
equivalent to the statement that d′(G) > 0 for every snark G. Stated with resistance, the
Grünbaum Conjecture is equivalent to the statement that for every graph G, d′(G) > 0 if
r(G) > 0. The following theorem gives a stronger relation.
Theorem 10. If there exists a snark G with d′(G) < 12r(G) + 1, then there exists a snark G
′
with d′(G) = 0.
B. Mohar et al.: Relating Embedding and Coloring Properties of Snarks 177
x y
x1x1
x2x2
y1y1
y2y2
0 1 2
3
456
7
8
9
Figure 4: Thickening an edge.
Proof. Suppose there exists a snark G which has an embedding into an orientable surface
with 2d′(G) < r(G) + 2.
We will construct a sequence of graphs G1 = G,G1, G2, . . . , Gk such that d′(Gi) > 1
for i < k, d′(Gk) ≤ 1, d′(Gi) ≤ d′(Gi−1)−1 for i = 2, . . . , k and r(Gi) ≥ r(Gi−1)−2 for
i = 2, . . . , k. Since k < d′(G) and r(G) > 2k − 2 we see that r(Gk) > 0. So Gk is a non
3-edge-colorable cubic graph which has an embedding of defect at most 1 into an orientable
surface. By Lemma 8 the Grünbaum Conjecture is false and therefore there exists a snark G′
with d′(G′) = 0.
Suppose we have an embedding Π(Gi) of Gi for which d′(Π) = d′(Gi). We replace a
bad edge e = xy in the embedding of Gi with a graph on 10 vertices (see Figure 4) to get a
graph Gi+1 with an induced embedding of a smaller modified defect (see Figure 4). In the
embedding of Gi we can assume we have facial walks W1, W2, W3, W4 which contain the
paths x1xyy1, y1yy2, y2yxx2 and x2xx1 respectively, where some of W1, W2, W3, W4 may
be equal. To define an embedding of Gi+1 we take facial walks of the embedding of Gi,
replace the paths x1xyy1, y1yy2, y2yxx2 and x2xx1 on the walks W1, W2, W3, W4 with the
paths x1654y1, y1432y2, y2210x2 and x2076x1 and add facial cycles 018970, 12381, 34583
and 56785. By appropriately choosing the bad edge e we can guarantee that the modified
defect decreases by at least one.
We distinguish four choices for the bad edge e. At each step we can make Choice 3 only
if we can not make Choices 1 or 2 and can make Choice 4 if we can not make Choices 1, 2,
or 3. As long as the defect of the embedding is more that 0 we can make one of the choices.
Choice 1: bad edge e = xy where x and y are bad vertices. In this case W1 = W2 =
W3 = W4.
To calculate the modified defect of the embedding of Gi+1 observe that bad edges in the
embedding of Gi+1 are bad edges of the embedding of Gi minus e plus bad pairs {70, 01},
{12, 23}, {34, 45} and {56, 67}. So d(Π(Gi+1)) = d(Π(Gi))−1+4 = d(Gi)+3. Since we
removed two bad vertices x and y and created no new bad vertices we have dV (Π(Gi+1)) =
dV (Π(Gi)) − 2 and therefore the modified defect is d′(Π(Gi+1)) ≤ d′(Π(Gi)) − 1. Since
d(Π(Gi)) = d′(G) we conclude that d′(Gi+1) ≤ d′(Gi)− 1.
Choice 2: bad edge with e = xy where x is a bad vertex and y is not. In this case
W1 = W3 = W4 and W2 6= W1.
178 Ars Mathematica Contemporanea 1 (2008) 169–184
The defect of the induced embedding of Gi+1 is
d(Π(Gi+1)) = d(Π(Gi))− 1 + 2 = d(Gi) + 1
and
dV (Π(Gi+1)) = dV (Π(Gi))− 1.
Therefore the modified defect is d′(Π(Gi+1)) = d′(Π(Gi))−1. We conclude that d′(Gi+1)≤
d′(Gi)− 1.
Choice 3: bad edge e = xy which appears twice along one facial walk. Since we can not
make choices 1 or 2 we can assume that W1 = W3 and W2 6= W1 and W4 6= W1 (but it is
possible that W2 = W4).
In the embeddings ofGi andGi+1 there are no bad vertices. The defect of the embedding
of Gi+1 is d(Π(Gi+1)) = d(Π(Gi))− 1 and therefore d′(Gi+1) ≤ d′(Gi)− 1.
Choice 4: e = xy which does not appear twice along one facial walk. Since we can not
make choices 1, 2, or 3 it is only possible that maybe W2 = W4.
In the embeddings ofGi andGi+1 there are no bad vertices. The defect of the embedding
of Gi+1 is d(Π(Gi+1)) = d(Π(Gi))− 1 and therefore d′(Gi+1) ≤ d′(Gi)− 1.
It remains to show that r(Gi+1) ≥ r(Gi) − 2. Suppose we have a minimum coloring c
of the graph Gi+1. We define a coloring c′ of Gi as follows: c′(f) = c(f) if f is not incident
with x or y and c′(x1x) = c(x16), c′(yy2) = c(2y2). We can color the edge f with one of
the colors 1, 2, 3 and color edges x20 and y14 with color 4. So r(Gi) ≤ r(Gi+1) + 2.
Theorem 10 implies that if Grünbaum’s conjecture is true, we can bound d′(G) from
below with r(G), which would be a very strong connection between the defect, which is a
topological property, and resistance, which is a coloring property. A similar bound holds for
the unmodified defect as shown below.
Corollary 11. The following statements are equivalent:
(1) The Grünbaum Conjecture is true.
(2) For all snarks G: d′(G) ≥ 12r(G) + 1.
(3) For all snarks G: d(G) ≥ 38r(G) +
3
4 .
Proof. It is obvious that either of (2) and (3) imply (1). For (2), the reverse holds by Theo-
rem 10.
To see that (3) follows from (1), observe that d(Π) ≥ 6dV (Π). From this fact we get
d′(Π) = d(Π) + 2dV (Π) ≤
4
3
d(Π)
and so d′(G) ≤ 43d(Π).
So, assuming (1) we obtain (2), and consequently
r(G) ≤ 2d′(G)− 2 ≤ 8
3
d(G)− 2
or equivalently 38r(G) +
3
4 ≤ d(G).
A similar result follows for Conjecture 2. If a cubic graph G is embeddable into an
orientable surface S we define the defect of G in S as
dS(G) = min{d(Π) | Π is an embedding of G into S}.
B. Mohar et al.: Relating Embedding and Coloring Properties of Snarks 179
and similarly the modified defect of G in S as
d′S(G) = min{d′(Π) | Π is an embedding of G into S}.
Theorem 12. If there exists a snark G embeddable into a surface S with dS(G) < r(G)2 then
there exists a snark G′ embeddable into S with dS(G′) = 0.
Proof. We follow the proof of Theorem 10. Note that when we thicken an edge in Gi, the
graph Gi+1 is embedded into the same surface.
Corollary 13. For every orientable surface S the following statements are equivalent:
(1) Conjecture 2 is true for S.
(2) For all snarks G embeddable into S: d′S(G) ≥
r(G)
2 .
(3) For all snarks G embeddable into S: dS(G) ≥ 38r(g).
The proof is similar to the proof of Corollary 11 and is omitted. Let us observe that the
bounds in Corollary 11 can be made slightly better since we can use Lemma 8(2) to strengthen
the base case, but here we can not since the proof of that lemma involves snarks which may
not be embeddable in S.
4 Larger face-width and blocking weight
We now give similar results for Conjecture 3. Let Π be an embedding of a cubic graph G
into a surface S and let k > 0 a fixed integer. Let G∗ be the dual of G in Π. A function
w : E(G) → Z+ is a k-blocking weight if for each cycle C in G∗, which is not contractible
in the surface S, we have
w∗(C) :=
∑
e∈E(C)
w(e) ≥ k.
Obviously, an embedding Π has face-width at least k if and only if the trivial function with
w(e) = 1 for each e ∈ E(G), is a k-blocking weight.
Let φ : Z+ → Z+ be the function defined recursively as follows. We set φ(1) = 0, and
for x ≥ 2 define recursively
φ(x) = 5φ
(⌈x
2
⌉)
+ 5φ
(⌊x
2
⌋)
+ 1. (1)
For a k-blocking weight w of an embedding Π, we define
dk(G,Π, w) =
∑
e∈E(G)
φ(w(e))
and set
dk(G,Π) = min{dk(G,Π, w) | w a k-blocking weight for Π}.
Finally, the k-defect of G in S is
dkS(G) = min{dk(G,Π) | Π an embedding of G into S}.
If G cannot be embedded in S, we set dkS(G) =∞.
180 Ars Mathematica Contemporanea 1 (2008) 169–184
x y
x1x1
x2x2
y1y1
y2y2
0 1 2 3
4567
Figure 5: Thickening an edge.
Theorem 14. Let k be an integer and S a fixed surface. If there exists a snark G embeddable
into S with dkS(G) <
r(G)
2 , then there exists a snark G
′ embeddable into S with face-width
at least k.
Proof. Suppose that there exists a snark G embeddable into S with dkS(G) <
r(G)
2 . We will
construct a sequence of graphs G0 = G,G1, G2, . . . , Gn such that dkS(Gi) > 0 for i < n,
dkS(Gn) = 0, and d
k
S(Gi+1) ≤ dkS(Gi)− 1 and r(Gi+1) ≥ r(Gi)− 2 for i = 0, . . . , n− 1.
These properties imply that n ≤ dkS(G). Since r(G) > 2dkS(G) ≥ 2n, the stated recursive
property for the resistances of consecutive terms also implies that r(Gn) > 0. So Gn is a
non-3-edge-colorable graph embedded into S with face-width at least k.
Again Gi+1 is constructed from Gi by thickening an edge. Suppose Gi is Πi-embedded
into S and wi is a k-blocking weight of Gi such that dkS(Gi) = d
k(G,Πi, wi). Let e be an
edge of Gi whose weight w(e) is maximum. Suppose wi(e) = w. We replace the edge e in
Gi as shown in Figure 5 to get a graph Gi+1 embedded in the same surface S. We define the
weight function wi+1 : E(Gi+1) → Z+ as follows. If f ∈ E(Gi), then wi+1(f) = wi(f).
For the new edges we set: wi+1(01) = wi+1(12) = wi+1(23) = wi+1(34) = wi+1(07) =
dw2 e and wi+1(45) = wi+1(52) = wi+1(56) = wi+1(61) = wi+1(67) = b
w
2 c.
It is easy to check that wi+1 is a k-blocking weight forGi+1 and that r(Gi) ≤ r(Gi+1)+
2. Since we have replaced one edge of weight w with five edges of weight dw2 e and five of
weight bw2 c, the definition (1) of the valuation function φ implies that
dkS(Gi+1) ≤ dk(Gi+1,Πi+1, wi+1) = dk(Gi,Πi, wi)− 1 = dkS(Gi)− 1.
This proves our claims and completes the proof.
Corollary 15. For a fixed surface S and an integer k, the following statements are equivalent:
(1) Conjecture 3 is true for S and k.
(2) If a snark G is embeddable into S, then dkS(G) ≥
r(G)
2 .
5 Snarks with large girth
Let G be a superposition of the Petersen graph. A vertex of G that arises from a vertex v of
P by replacing it with a trivial supervertex S(v) will be called an original vertex. Each edge
B. Mohar et al.: Relating Embedding and Coloring Properties of Snarks 181
0
1
2
3
4
5
6
7
8
9
Figure 6: Cyclically 4-edge-connected graphs G4.
incident with an original vertex will be called an original edge. A connected subgraph of G
which is induced by nontrivial supervertices and superedges between them is called a block.
We will describe cycles inG. If a cycleC contains a path x1 . . . xk this will be denoted by
C = ∗x1 . . . xk∗. If a cycle enters a block in a supervertex S(x2) from an original vertex x1
and leaves this block from a supervertex S(y1) to an original vertex y2, this will be denoted
by C = ∗x1x2.y1y2∗. It is possible that x2 = y1 in which case we will sometimes write
C = ∗x1x2y2∗. There are no original vertices on C between x1 and y2.
In [4] two families of snarks of large girth were constructed. The first family has cyclic
edge-connectivity four. All these graphs can be expresses as a proper superposition of the
Petersen graph where we assign trivial supervertices to vertices 0, 3, 6, 7, 8, 9 of P (see also
Figure 6). Let G4 be the set of all cubic graphs that can be obtained in this way.
Theorem 16. If G ∈ G4 then G has no polyhedral embeddings into orientable surfaces.
Proof. Let G ∈ G4 and suppose that it is polyhedrally embedded into an orientable surface.
We use the notation from Figure 6.
Look at the facial cycles on the edges 01 and 81. There are at least three distinct facial
cycles on these two edges, otherwise the embedding would not be polyhedral.
We now show that there are exactly three. Suppose we have four facial cycles A =
∗01.23∗, B = ∗01.27∗, C = ∗81.27∗ and D = ∗81.23∗ Since the embedding is polyhe-
dral, the cycle C must be C = 81.2768 (otherwise it would intersect the facial cycle which
contains the path 867 twice) and the cycle A must be A = 01.2390 (otherwise it would in-
tersect the facial cycle which contains the path 390 twice). Since B already intersects cycles
A and C it can not use the edge 43 or 48, therefore it must be B = 01.2750 and simi-
larly D = 81.2348. There is another facial cycle which contains the vertex 3. It must be
F = 439675.4 since the embedding is polyhedral. Since the embedding is orientable, we can
consistently orient the facial cycles. Suppose that F is oriented so that the edges 43 and 67
are in the direction of the orientation. Then the cycle D is oriented so that the edges 34 and
182 Ars Mathematica Contemporanea 1 (2008) 169–184
0
1
2
3
4
5
6
7
8
9
Figure 7: A cyclically 5-edge-connected graph.
81 are in the direction of the orientation. Finally the cycle C is directed so that the edges 18
and 67 are in the direction of the orientation. This is a contradiction since the facial cycles C
and F are oriented in the same direction on the edge 67.
By symmetry we have exactly three facial cycles at the edges from the other superver-
tices. The facial cycles which contain original edges therefore induce an embedding of the
underlying Petersen graph. Since the embedding of G is orientable we have a consistent ori-
entation of cycles. We use this orientation in the induced embedding of P . Since facial walks
are oriented consistently on original edges of G, this orientation is consistent on all edges of
P and so the embedding is orientable.
Suppose that in the induced embedding of the Petersen graph we have two facial cycles
A and B which have k + 1 edges in common. This implies that at least k of these edges
correspond to superedges in G. It follows that the induced embedding of the Petersen graph
has defect at most 2, since in G we have two superedges. This contradicts Lemma 5.
A graph G is in G5 if it is a proper superposition of the Petersen graph where we assign
trivial supervertices to the vertices 6, 7, 8, 9 and additionally trivial superedges to the edges
54 and 12 (see also Figure 7).
If a cycle C enters a block on a supervertex x2 from an original vertex x1, then it uses
some vertices from a supervertex x3 and then leaves the block from a supervertex x3 to an
original supervertex x4, this will be denoted by C = ∗x1.x2.x3.x4∗.
Theorem 17. If G ∈ G5 then G has no polyhedral embeddings into orientable surfaces.
Proof. Let G ∈ G5 and suppose it has a polyhedral embedding into an orientable surface.
Similarly as in the proof of the previous theorem we first show that this embedding induces
an embedding of the underlying Petersen graph. We use the notation of Figure 7. Call the
supervertices 0, 1, 2 with superedges between them the lower block and the supervertices
3, 4, 5 with superedges between then the upper block.
B. Mohar et al.: Relating Embedding and Coloring Properties of Snarks 183
Assume that on the edges 75 and 45 we have four distinct facial cycles, A = ∗75.0∗,
B = ∗75.0∗, C = ∗45.0∗ and D = ∗45.0∗. Since the embedding is polyhedral, there must
be two distinct facial cycles which enter the lower block on the edge 90. This implies that not
all four of A,B,C,D can leave the lower block on the edges 12 and 18.
CASE 1: Assume that only a facial cycle, which contains the edge 75, say A, leaves the
lower block on the edge 09. Since the embedding is polyhedral, we have A = 75.0967 and
B = ∗275.0.1∗ and we can assume C = ∗45.0.12∗ and D = ∗45.0.1.8∗. The cycle B can
not leave the lower block on the edge 28 since then there would be a facial cycle at vertex 6
which would intersect it twice. So we have B = 275.0.12. The cycle C can not leave the
upper block on the edge 48 since it already intersects the cycle D and also not on the edge 39
since it would have to continue on the path 3968. Similarly it can not leave on the edge 27,
so it must be C = 45.0.12.3.4. We have another cycle F which enters the lower block on the
edge 81, F = ∗81.093∗. This cycle will intersect with the cycle which contains the path 869
twice, a contradiction to the assumption that the embedding is polyhedral.
CASE 2: Assume that only a facial cycle, which contains the edge 45, say C, leaves the
lower block on the edge 09. So C = ∗45.09∗, D = ∗45.0.1∗, A = ∗75.0.18∗ and B =
∗75.0.12∗. Since the embedding is polyhedral we have A = 75.0.1867 and B = 75.0.127.
If we had D = ∗45.0.12∗ then there would be another facial cycle F = ∗90.184∗ which
would intersect the facial cycle which contains the path 869 twice, a contradiction. So we
have D = 45.0.184 and C = ∗45.093∗. There is a facial cycle F = ∗21.096∗. If we had
F = ∗21.0967∗, then F and A would intersect twice, and if we had F = ∗21.0968∗ then the
cycles A, D and F could not be consistently oriented.
CASE 3: Assume there that two cycles, say A and C, which leave the lower block on
the edge 09. Again we have A = 75.0967, B = ∗275.0.1∗, C = ∗45.0.93∗ and D =
∗45.0.1∗. If the cycle B would leave the lower block on the edge 18, then it would be
B = ∗275.0.184∗ and it would intersect the cycle which contains the path 867 twice. So we
have B = ∗275.0.184∗ and C = 45.0.184. Now we have a facial cycle F = ∗218693∗ and
we get a contradiction since the cycles C, D and F can not be consistently oriented.
So we have that there are exactly three facial cycles on the edges 45 and 75. By sym-
metry the same holds for the edges at supervertices 1, 2 and 4. Since the embedding of G
is polyhedral and orientable we get that the facial cycles which contain the original edges of
G induce an orientable embedding of P , which has defect at most 4. This again contradicts
Lemma 5.
References
[1] D. Blanuša, Problem četiriju boja, Glasnik Mat.-Fiz. Astr. 2 (1946), 31–42.
[2] M. DeVos, L. Goddyn, B. Mohar, D. Vertigan and X. Zhu, Coloring-flow duality of embedded
graphs, Trans. Amer. Math. Soc. 357 (2005), 3993–4016.
[3] B. Grünbaum, Conjecture 6, in W. T. Tutte (ed.) Recent Progress in Combinatorics, Academic
Press, New York, 1969, p. 343.
[4] M. Kochol, Snarks without small cycles, J. Comb. Theory Ser. B 67 (1996), 34–47.
[5] B. Mohar and C. Thomassen, Graphs on Surfaces, The Johns Hopkins University Press, Baltimore
and London, 2001.
[6] B. Mohar and A. Vodopivec, On polyhedral embeddings of cubic graphs, Combin. Probab. Com-
put. 15 (2006), 877–893.
[7] B. Mohar, A. Vodopivec, The genus of Petersen powers, preprint.
184 Ars Mathematica Contemporanea 1 (2008) 169–184
[8] A. Orbanić, T. Pisanski, M. Randić, B. Servatius, Blanuša double, Math. Commun. 9 (2004),
91–103.
[9] E. Steffen, Measurements of edge-uncolorability, Discrete Math. 280 (2004), 191–214.
[10] G. Szekeres, Polyhedral decompositions of cubic graphs, Bull. Austral. Math. Soc. 8 (1973), 367–
387.
[11] F. C. Tinsley, J. J. Watkins, A study of snark embeddings, in Graphs and Applications (Boulder,
Colo., 1982), Wiley-Intersci. Publ., Wiley, New York, 1985, 317–332.