Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 255–269
Facial parity edge colouring
Július Czap
Department of Applied Mathematics and Business Informatics, Faculty of Economics,
Technical University of Košice, B. Němcovej 32, 040 01 Košice, Slovakia
and
Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University
Jesenná 5, 040 01 Košice, Slovakia
Stanislav Jendrol’
Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University
Jesenná 5, 040 01 Košice, Slovakia
František Kardoš
Institute of Mathematics, Faculty of Science, Pavol Jozef Šafárik University
Jesenná 5, 040 01 Košice, Slovakia
and
Institute for Theoretical Computer Science (ITI), Faculty of Mathematics and Physics,
Charles University, Malostranské Náměstı́ 25, 118 00 Prague, Czech Republic
Received 10 December 2009, accepted 23 December 2010, published online 26 May 2011
Abstract
A facial parity edge colouring of a connected bridgeless plane graph is an edge colouring
in which no two face-adjacent edges (consecutive edges of a facial walk of some face)
receive the same colour, in addition, for each face α and each colour c, either no edge or an
odd number of edges incident with α is coloured with c. From Vizing’s theorem it follows
that every 3-connected plane graph has a such colouring with at most ∆∗+1 colours, where
∆∗ is the size of the largest face. In this paper we prove that any connected bridgeless plane
graph has a facial parity edge colouring with at most 92 colours.
Keywords: plane graph, facial walk, edge colouring
Math. Subj. Class.: 05C10, 05C15
E-mail addresses: julius.czap@tuke.sk, julius.czap@upjs.sk (Július Czap), stanislav.jendrol@upjs.sk
(Stanislav Jendrol’), frantisek.kardos@upjs.sk (František Kardoš)
Copyright c© 2011 DMFA Slovenije
256 Ars Math. Contemp. 4 (2011) 255–269
1 Introduction
One of the motivations for this paper has come from recent papers of Bunde et al. [1, 2]
who introduced parity edge colourings of simple graphs. Studying the parity of the usage
of colours along walks suggested two edge-colouring parameters that have interesting
properties and applications. A parity walk in an edge colouring of a simple graph is a walk
along which each colour is used an even number of times. Bunde et al. [2] introduced two
parameters. Let p(G) be the minimum number of colours in an edge colouring ofG having
no parity path (a parity edge colouring). Let p̂(G) be the minimum number of colours in an
edge colouring of G in which every parity walk is closed (a strong parity edge colouring).
Since incident edges of the same colour would form a parity path of length 2, every parity
edge colouring is a proper edge colouring, and hence p(G) ≥ χ′(G), where χ′(G) is the
chromatic index of G. Since a path is an open walk, no strong parity edge colouring has
a parity path. Hence, every strong parity edge colouring is a parity edge colouring and
p̂(G) ≥ p(G) for every graph G. Although there are graphs G with p̂(G) > p(G) [2], it
remains unknown how large p̂(G) can be when p(G) = k. Elementary results on these
parameters appear in [2]. In [1] it is proved that p̂(Kn) = 2dlog(n)e−1 for all n. Moreover,
the optimal strong parity edge colouring of the complete n-vertex graphKn is unique when
n is a power of 2. The authors of [2] mentioned that computing p(G) or p̂(G) is NP-hard
even when G is a tree. Clearly, the parity edge colouring is such a colouring that each path
uses at least one colour an odd number of times.
The vertex version of this problem (strong parity vertex colouring) with some restric-
tions was introduced in [3]. The authors of [3] conjectured that there is a constant K such
that the vertices of any 2-connected plane graph can be coloured with at most K colours
in such a way that for each face α and each colour c, either no vertex or an odd number of
vertices incident with α is coloured with c.
Another motivation for this work has come from the papers of Pyber [5] and Mátrai [4].
A graph is called odd if the degree of its vertices is odd or zero. Pyber raises the problem
of edge covering with odd subgraphs in [5] as the counterpart of even subgraph covering
problems. He proved that the edges of every finite simple graph can be covered by at
most 4 edge-disjoint odd subgraphs; moreover, if the number of vertices is even then 3 odd
subgraphs are sufficient. For not necessarily edge-disjoint coverings we have the following
question: Is it true that every graph can be covered by at most 3 odd subgraphs? Mátrai in
[4] showed that every finite simple graph can be covered by 3 odd subgraphs and he found
an infinite sequence of finite simple connected graphs not coverable by 3 edge-disjoint odd
subgraphs.
Pyber’s result implies the following: The edges of any 3-connected plane graph G can
be coloured by at most 4 colours in such a way that for each face α and each colour c, either
no edge or an odd number of edges incident with α is coloured with c. It is sufficient to
consider the dual G∗ of G and its edge cover with at most 4 edge-disjoint odd subgraphs.
This cover induces the required colouring of G.
If we add a requirement that such a colouring must be proper, then it is not clear whether
there exists a colouring with K colours, where K is an absolute constant. From Vizing’s
theorem [6] it follows that every 3-connected plane graph G has such a colouring which
uses at most ∆∗ + 1 colours, where ∆∗ is the size of the largest face. Consider a proper
edge colouring of the dual graph G∗. This colouring induces a colouring of G in a natural
way. It is such a colouring in which, for each face α of G, all the edges in the boundary of
α have distinct colours.
J. Czap, S. Jendrol’and F. Kardoš: Facial parity edge colouring 257
In this paper we show that each connected bridgeless plane graph has a facial parity
edge colouring using at most 92 colours.
2 Notation
Let us introduce the notation used in this paper. A graph which can be embedded in the
plane is called planar graph; a fixed embedding of a planar graph is called plane graph.
A bridge is an edge whose removal increases the number of components. A graph
which contains no bridge is said to be bridgeless. In this paper we consider connected
bridgeless plane graphs, multiple edges and loops are allowed.
Let G = (V,E, F ) be a connected plane graph with the vertex set V , the edge set E,
and the face set F . The degree of a vertex v, denoted by deg(v), is the number of edges
incident with v, each loop counting as two edges. A k-vertex is a vertex of degree k. For a
face α, the size of α, deg(α), is defined to be the length of its facial walk, i.e. the shortest
closed walk containing all edges from the boundary of α. We often say k-face for a face of
size k.
Given a graph G and one of its edges e = uv (the vertices u and v do not have to be
different), the contraction of e denoted byG/e consists of replacing u and v by a new vertex
adjacent to all the former neighbours of u and v, and removing the loop corresponding to
the edge e. (We keep multiple edges if they arise.) Analogously we define the contraction
of the set of edges H = {e1, . . . , ek} and we denote it by G/{e1, . . . , ek} or G/H .
Two faces are adjacent if they share an edge. Two (distinct) edges are face-adjacent if
they are consecutive edges of a facial walk of some face α.
A k-edge colouring of a graph G is a mapping ϕ : E(G) → {1, . . . , k}. The facial
parity edge (FPE) colouring of a connected bridgeless plane graph is such an edge
colouring that no two face-adjacent edges receive the same colour, in addition, for each
face α and each colour c, either no edge or an odd number of edges incident with α is
coloured with c.
Question 2.1. What is the minimum number of colours χ′fp(G) that a connected bridgeless
plane graph G has a facial parity edge colouring with at most χ′fp(G) colours?
The number χ′fp(G) is called the facial parity chromatic index of G.
3 Results
Theorem 3.1. Let G be a connected bridgeless plane graph. Then
χ′fp(G) ≤ 92.
The proof uses the method of discharging. Let G be a counterexample with minimal
number of edges, then minimal number of 1-faces, and then minimal number of 2-faces. If
G is a single cycle of length d, d ≤ 5, we use exactly d colours. We consider this to be the
first step of induction and call this case trivial.
First, we prove several structural properties of G.
We say that a face α is small if 1 ≤ deg(α) ≤ 44 and a face β is big if deg(β) ≥ 45.
3.1 Reducible configurations
We find such (forbidden) subgraphs H of G that the facial parity edge colouring of G/H
using at most 92 colours can be extended to a required colouring of G using at most 92
258 Ars Math. Contemp. 4 (2011) 255–269
colours, which is a contradiction to G being a counterexample. In the sequel, whenever we
speak about an FPE colouring, we always mean an FPE colouring using at most 92 colours.
3.1.1 1-faces
Claim 3.2. Each vertex of G is incident with at most one 1-face.
Proof. Let v be a vertex incident with at least two 1-faces α1 and α2. If we split v into two
vertices v1 and v2 in such a way that α1 and α2 become a 2-face α and face-adjacency of
all edges incident with v is preserved, we obtain a graph G′, see Figure 1. It has the same
number of edges as G, but fewer 1-faces. Thus, it is not a counterexample and we can find
an FPE colouring ϕ′ of G′. It induces an edge colouring ϕ of G in a natural way. It is easy
to see that ϕ is an FPE colouring.
v
α1 α2 −→ α
v1
v2
γ
α
v
−→ α′
Figure 1: A vertex incident with at least two 1-faces can be split into two vertices, reducing
the number of 1-faces. Similarly, one can reduce a 1-face and a d-face (2 ≤ d ≤ 4) incident
with the same vertex.
Claim 3.3. Each vertex of G incident with a 1-face is not incident with any other d-face
for 2 ≤ d ≤ 4.
Proof. We use the same reduction as in the proof of Claim 3.2. We split the vertex v
incident with a 1-face γ and a d-face α (2 ≤ d ≤ 4) in such a way that the faces α and
γ become a (d + 1)-face α′ and face-adjacency of all edges incident with v is preserved,
see Figure 1 for illustration. Let the reduced graph be G′. It has fewer 1-faces than G,
therefore, it has an FPE colouring ϕ′. The face α′ has size at most five, therefore, its edges
are coloured using d + 1 different colours. Thus, the colouring ϕ of G induced by the
colouring ϕ′ of G′ is an FPE colouring, too.
Claim 3.4. Each vertex of G incident with a 2-face is not incident with any d-face for
2 ≤ d ≤ 3.
Proof. We use the same reduction as in the proofs of Claims 3.2 and 3.3. We omit the
details.
3.1.2 Small faces
Claim 3.5. There are no two adjacent small faces in G.
Proof. Let α1 and α2 be two adjacent small faces in G.
If both α1 and α2 are 1-faces, the graph consists of a single vertex and a loop; it has an
FPE colouring using 1 colour.
J. Czap, S. Jendrol’and F. Kardoš: Facial parity edge colouring 259
Let α1 be a 1-face and α2 be a d-face, d ≥ 2; let e be the loop they share, see Figure 2.
Then the graph G′ = G/e has fewer edges than G, therefore, it has an FPE colouring ϕ′.
Let α′ be a face in G′ corresponding to α1 and α2 in G. Since α2 is a small face, at most
43 colours occur on the edges incident with α′. To extend the colouring ϕ′ of G′ to an FPE
colouring of G, it suffices to colour the edge e with any colour that does not occur on α′.
Let α1 and α2 be two small faces of size at least 2 and let e be the edge they share, see
Figure 2. The graph G′ = G/e has fewer edges than G, therefore, it has an FPE colouring
ϕ′. Let α′1 and α
′
2 be the faces of G
′ corresponding to the faces α1 and α2 in G. (Since α1
and α2 are faces of size at least 2, the size of α′1 and α
′
2 is at least 1.)
Consider the set of colours different from the colours occurring on the edges ofα′1 andα
′
2
(the colours admissible for the edge e). Since α1 and α2 are small, at most 2 · (44−1) = 86
colours occur on the edges incident with α′1 and α
′
2. Hence, there is an admissible colour
c. We can extend ϕ′ to an FPE colouring ϕ of G by setting ϕ(e) = c.
α1 α2
e
−→ α′ α1 α2e −→ α′1 α′2
Figure 2: Two adjacent small faces form a reducible configuration: one can contract the
edge they share.
Claim 3.6. Let β be a big face adjacent to two small faces α1 and α2. Let ei be an edge
incident with β and αi, i = 1, 2. Then e1 and e2 are face-adjacent.
Proof. Let e1 and e2 not be face-adjacent. See Figure 3 for illustration. The graph
G′ = G/{e1, e2} has fewer edges than G, therefore, it has an FPE colouring ϕ′. Let α′1,
α′2, β
′ be the faces of G′ corresponding to the faces α1, α2, β in G, respectively.
α1 α2βe1 e2 −→ α′1 α′2β′
Figure 3: A big face β adjacent to two different small faces α1 and α2 forms a reducible
configuration unless the edges e1 and e2 are face-adjacent.
We extend the colouring ϕ′ of G′ to an FPE colouring of G in the following way:
Consider the set of colours different from the colours occurring on the edges of α′1 and α
′
2;
also different from the colours occurring on the edges of G′ corresponding to the edges of
G face-adjacent to e1 and e2. There are at least 92− 2 · (44− 1)− 4 = 2 such colours, say
c1 and c2. If at least one of them, say ci, already occurs on β′, we set ϕ(e1) = ϕ(e2) = ci.
If none of them occurs on β′, we set ϕ(ei) = ci, i = 1, 2.
Claim 3.7. Each big face is adjacent to at most one 1-face.
Proof. It follows from Claims 3.2 and 3.6.
260 Ars Math. Contemp. 4 (2011) 255–269
Claim 3.8. Each big face is adjacent to at most two small faces.
Proof. Let a big face β be adjacent to small faces α1, α2, and α3. Consider the edges that
β shares with αi, i = 1, 2, 3. It is easy to see that there must be a pair of edges ei and ej ,
incident to αi and αj , respectively (i 6= j), which are not face-adjacent. It is a contradiction
with Claim 3.6.
3.1.3 Chains of 2-vertices
Claim 3.9. There is no chain consisting of at least 5 consecutive 2-vertices in G.
Proof. Let v0e0v1e1 . . . vpepvp+1 be a chain consisting of p vertices v1, . . . , vp of degree
2, where p ≥ 5. The graph G′ = G/{e1, e2, e3, e4} has an FPE colouring ϕ′. Let e′0 and
e′5 be the edges in G
′ corresponding to the edges e0 and e5 in G. Let ϕ′(e′0) = c1 and
ϕ′(e′5) = c2. The FPE colouring ϕ
′ of G′ can be extended to an FPE colouring ϕ of G by
setting ϕ(e2) = ϕ(e4) = c1 and ϕ(e1) = ϕ(e3) = c2, see Figure 4.
e0 e1 e2 e3 e4 e5 −→ e′0 e′5
c1 c2 −→ e0 e1 e2 e3 e4 e5
c1 c2 c1 c2 c1 c2
Figure 4: A chain of (at least) five 2-vertices is a reducible configuration.
A d-face α is hanging on a vertex v, if all vertices incident with α are 2-vertices except
for the vertex v. By Claim 3.9 we have d ≤ 5. (If deg(v) = 2, the graph G consists of a
single cycle of length at most 5, which is the trivial case).
We colour the vertices of G with black, blue and white colour in the following way:
Let all 2-vertices be black, all 3-vertices be blue and all k-vertices for k ≥ 6 be white.
A 4-vertex v is black if there is a face hanging on it, else it is white. See Figure 5 for
illustration of all types of black vertices.
Figure 5: A vertex is black, if it is a 2-vertex, or a 4-vertex with a hanging face.
A 5-vertex v is blue, if there is a face hanging on it, else it is white.
Observe that any 2-vertex v is incident with two faces. We say v is bad for both faces it
is incident with. Any black 4-vertex v is incident with a small face α of size at most 5 and
two other faces. The face β adjacent to α must be big (see Claim 3.5); the vertex v occurs
twice on the facial walk of β. The other face γ can be big or small. We say v is bad for the
face γ.
Claim 3.10. For any face α, there is no chain of at least 5 consecutive vertices bad for α.
Each chain of bad vertices contains at most one bad 4-vertex.
J. Czap, S. Jendrol’and F. Kardoš: Facial parity edge colouring 261
Proof. Let v0e0v1e1v2e2v3e3v4e4v5e5v6 be a subpath of the facial walk of α containing
5 vertices v1, . . . , v5 bad for α. It is easy to see that all the edges e0, . . . , e5 are incident
with the same face β (β 6= α). If at least two of v1, . . . , v5 are bad 4-vertices, we come to a
contradiction with Claim 3.5 or with Claim 3.6. If none of them is a 4-vertex, we are in the
case of Claim 3.9. If precisely one of them is a 4-vertex, say vi, it is incident with a small
face γ of size d ≤ 5.
The graph G′ = G/{e1, e2, e3, e4} has an FPE colouring ϕ′. Let e′0 and e′5 be the
edges in G′ corresponding to the edges e0 and e5 in G; let α′, β′, γ′ be the faces in G′
corresponding to the facesα, β, γ inG; let v′ be the vertex inG′ corresponding to v1, . . . , v5
in G. Let ϕ′(e′0) = c1 and ϕ
′(e′5) = c2. Since e
′
0 and e
′
5 are face-adjacent in G
′, c1 6= c2.
To extend ϕ′ to an FPE colouring of G, we proceed in the following way:
If i = 1, 3, or 5, we simply set ϕ(e2) = ϕ(e4) = c1 and ϕ(e1) = ϕ(e3) = c2.
If i = 2 or i = 4, we set ϕ(e2) = ϕ(e4) = c1 and ϕ(e1) = ϕ(e3) = c2 and switch the
order of colours of edges incident with γ′, see Figure 6 for illustration (here the small face
γ is a bigon).
e0 e1 e2 e3 e4 e5 −→ e′0 e′5
c1 c2
c3 c4
−→ e0 e1 e2 e3 e4 e5
c1 c2 c1 c2 c1 c2
c3 c4
e0 e1 e2 e3 e4 e5 −→ e′0 e′5
c1 c2
c3 c4
−→ e0 e1 e2 e3 e4 e5
c1 c2 c1 c2 c1 c2
c4 c3
Figure 6: A chain of (at least) five bad black vertices is a reducible configuration as well.
Claim 3.11. Let v be a black vertex bad for a small face α. If v is a 4-vertex, then the face
hanging on it is a 1-face.
Proof. Let v be a black 4-vertex, let γ be the face hanging on v of size at least 2 and let
e1 and e2 be the edges of α incident with v. It is easy to see that the edges e1 and e2 are
incident with the same big face, say β. See Figure 7 for illustration.
There is an edge eγ incident with γ and β, which is not face-adjacent to eα ∈ {e1, e2},
which is a contradiction with Claim 3.6.
α
v
β
γ
eα
eγ
α
v1 v2
β
γ
eα
eγ
Figure 7: Reducible pairs of edges (eγ and eα). For details see Claims 3.11 and 3.12.
262 Ars Math. Contemp. 4 (2011) 255–269
Claim 3.12. Let α be a small face sharing at least two bad black vertices with a big face
β. Then all the bad black vertices incident with α and β are 2-vertices.
Proof. Let v1 and v2 be black vertices incident with α and β. If v1 is a 4-vertex, it is bad
for α, therefore, there is a small face γ hanging on v1, adjacent to β. By Claim 3.11, the
face γ is a 1-face. Thus, we can find an edge (a loop) eγ incident with γ and β and an edge
eα incident with α and β, which are not face-adjacent. This is a contradiction with Claim
3.6. See Figure 7 for illustration.
Claim 3.13. Let v be a black vertex bad for a small d-face α, d ∈ {2, 3, 4}. Then v is a
2-vertex.
Proof. Let v be a black 4-vertex, let γ be the face hanging on v. By Claim 3.11, the face
γ is a 1-face. On the other hand, by Claim 3.3, the face γ cannot be a 1-face, which is a
contradiction.
Claim 3.14. If a big face β shares a 2-vertex v with a small face α, then β is not adjacent
to any other small face.
Proof. It follows immediately from Claim 3.6.
Claim 3.15. Let γ be a d-face, d ∈ {2, 3, 4, 5}, hanging on a vertex v, adjacent to a big
face β. Then β is not adjacent to any other small face.
Proof. It follows immediately from Claim 3.14.
3.2 Discharging rules
If G is a minimal counterexample then it contains no reducible configuration. Let the
initial charge of each vertex be ψ(v) = deg(v) − 6 and the initial charge of each face be
ψ(α) = 2 deg(α)− 6. From Euler’s formula we can easily derive that∑
α∈F
(2 deg(α)− 6) +
∑
v∈V
(deg(v)− 6) = −12.
It is obvious that all the negative charge is in the vertices of degree 2, 3, 4, and 5 and in
the faces of size 1 and 2.
Rule 1: Let β be a big face.
• If β is adjacent to a single small face α, it sends 3 units of charge to α.
• If β is adjacent to two small faces α1 and α2, such that deg(α1) ≤ deg(α2), it sends
2 units of charge to α1 and 1 unit of charge to α2. (If deg(α1) = deg(α2), it is
decided arbitrarily.)
Rule 2: Let β be a big face.
• It sends 2 units of charge to any black vertex bad for β.
• It sends 1 unit of charge to any other black, blue, or white vertex incident with β.
(Multiply incident vertices are considered as different.)
Rule 3: Let α be a small face.
J. Czap, S. Jendrol’and F. Kardoš: Facial parity edge colouring 263
• It sends 2 units of charge to any black vertex bad for α.
• It sends 1 unit of charge to any other black or blue vertex incident with α.
Rule 4: Let v be a black 4-vertex.
• It sends 2 units of charge to the incident small hanging face γ.
Rule 5: Let v be a blue 5-vertex.
• It sends 2 units of charge to the incident small hanging face γ.
Rule 6: Let v be a k-vertex, k ≥ 6.
• It sends 2 units of charge to any incident small hanging face γ.
3.3 Analysis of the discharging process
3.3.1 Vertices
Every 2-vertex is black and bad for both faces incident with it, hence it receives 2 units of
charge from both incident faces (Rules 2 and 3). Its new charge is −4 + 2 + 2 = 0.
Every 3-vertex is blue, hence it receives 1 unit of charge from all the three incident
faces (Rules 2 and 3). Its new charge is −3 + 3 · 1 = 0.
Every black 4-vertex v receives 2 units of charge from the face it is bad for (Rules 2 and
3) and 2 · 1 units of charge from the doubly-incident big face β (Rule 2). It sends 2 units of
charge to the hanging face γ (Rule 4). The new charge of v is −2 + 2 + 2 · 1− 2 = 0.
Every white 4-vertex is incident with at least 2 big faces (see Claim 3.5), therefore, its
new charge is at least −2 + 2 · 1 = 0.
Every blue 5-vertex v is incident with a hanging face γ, doubly-incident with a big face
β and incident with two more faces α1 and α2. Therefore, v receives 4 · 1 units of charge
from the incident faces (Rules 2 and 3). It sends 2 units of charge to γ (Rule 5). Therefore,
the new charge of v is −1 + 4 · 1− 2 = 1.
Every white 5-vertex is incident with at least 3 big faces (see Claim 3.5), therefore, its
new charge is at least −1 + 3 · 1 = 2.
Every (white) k-vertex v, k ≥ 6, has non-negative initial charge. It receives charge
from big faces (Rule 2) and sends charge to the hanging faces γ1, . . . , γr (Rule 6). For each
hanging face γi, the adjacent big face βi is doubly-incident to v. The faces βi and βj are
different for different γi and γj (see Claims 3.6 and 3.7). Therefore, the new charge of v is
at least r · (2 · 1− 2) = 0.
3.3.2 1-faces
Let γ be a 1-face. It is adjacent to a big face β and it is hanging on a vertex v. The face β
is adjacent to at most one 1-face (Claim 3.7). Therefore, it sends at least 2 units of charge
to the face γ (Rule 1).
If the vertex v is a 2-vertex, we get the trivial graph, which is not a counterexample.
If the vertex v is a 3-vertex, the third edge incident with v is a bridge in G, which is not
allowed. Therefore, deg(v) ≥ 4 and the vertex v sends 2 units of charge to the face γ
(Rules 4 – 6). The new charge of γ is at least −4 + 2 + 2 = 0.
264 Ars Math. Contemp. 4 (2011) 255–269
3.3.3 2-faces
Let α be a 2-face. Its initial charge is−2. Let v1 and v2 be the vertices incident with α. The
face α is adjacent to at most two faces, which must be big (see Claim 3.5). Consider the
number of black vertices bad for α. Note that by Claim 3.13 each such vertex is a 2-vertex.
See Figure 8 for illustration.
1. Let both v1 and v2 be black and bad. Then the graph G consists of a single cycle on
two vertices, which is not a counterexample.
2. Let v1 be a black 2-vertex. Then α is adjacent to a single big face β. The big face β
is not adjacent to any other small face (see Claim 3.14). Therefore, β sends 3 units
of charge to α (Rule 1). The face α sends 2 units of charge to v1 and at most 1 unit
of charge to v2 (Rule 3). On the other hand, α is hanging on v2, therefore, it receives
2 units of charge from v2 (Rules 4 – 6). Note that v2 cannot be a 3-vertex, otherwise
there would be a bridge inG. The new charge of α is at least−2−2−1+2+3 = 0.
3. Let none of v1 and v2 be black and bad. Consider the number of faces adjacent to α.
If α is adjacent to a single big face β, then β is not adjacent to any other small face.
Therefore, β sends 3 units of charge to α. Moreover, in this case none of v1 and v2
can be neither black nor blue. The new charge of α is −2 + 3 = 1.
If α is adjacent to two big faces β1 and β2, the face α sends at most 2 · 1 units of
charge to v1 and v2. The big face βi, i = 1, 2, is not adjacent to any other small
face of size at most 2 (see Claims 3.3, 3.4, and 3.6). Therefore, by Rule 1, the face
βi, i = 1, 2, sends at least 2 units of charge to α. The new charge of α is at least
−2− 2 · 1 + 2 · 2 = 0.
α
v2
v1
β α
v2
v1
β α
v2
v1
β1 β2
Figure 8: Different possible neighbourhoods of a 2-face α.
3.3.4 3-faces
Let α be a 3-face. Its initial charge is 0. Let v1, v2, v3 be the vertices incident with α.
(They do not have to be pairwise different.) Consider the number of black vertices bad for
α. Note that by Claim 3.13 each such vertex is a 2-vertex. See Figure 9 for illustration.
1. Let all the three vertices v1, v2, v3 be black and bad. Then the graph G consists of a
single cycle on three vertices, which is not a counterexample.
2. Let v2 and v3 be black and bad. Then all the three edges of α are incident with
the same big face β and α is hanging on v1. Then by Claim 3.15 the face β sends
3 units of charge to α (Rule 1). The face α then sends 2 · 2 units of charge to
the 2-vertices v2, v3 and at most 1 unit of charge to the vertex v1 (Rule 3). If the
vertex v1 is a 3-vertex, the third edge incident with it is a bridge in G. Therefore
J. Czap, S. Jendrol’and F. Kardoš: Facial parity edge colouring 265
deg(v1) ≥ 4 and v1 sends 2 units of charge to α (Rules 4 – 6). The new charge of α
is 3− 2 · 2− 1 + 2 = 0.
3. Let v3 be black and bad. Let β1 be the big face incident with the edge v1v2 and β2
be the big face incident with the edges v2v3 and v3v1.
The face β2 sends 3 units of charge to α, β1 sends at least 1 unit of charge to α. The
face α then sends 2 units of charge to v3 and at most 1 unit of charge to v1 and v2.
The new charge of α is at least 3 + 1− 2− 2 · 1 = 0.
4. Let none of the vertices v1, v2, v3 be black and bad. Consider the number of faces
adjacent to α.
If there are three different faces adjacent to α (they must be big, see Claim 3.5) then
the face α receives at least 1 unit of charge from each of them and sends at most 1
unit of charge to each incident vertex. Hence, the new charge of α is at least 0.
If there is a big face β sharing at least two edges with α, these edges are not face-
adjacent in β. Therefore, β is not adjacent to any other small face, thus, it sends 3
units of charge to α. The new charge of α is non-negative again.
β
v1
v2v3
α
β2
β1
v1 v2
v3
α
β2
β1β3 v1
v2
v3 α
Figure 9: Different possible neighbourhoods of a 3-face α.
3.3.5 4-faces
Let α be a 4-face. Its initial charge is 2. Let v1, v2, v3, v4 be the vertices incident with α.
(They do not have to be pairwise different.) Consider the number of black vertices bad for
α. Note that by Claim 3.13 each such vertex is a 2-vertex. See Figure 10 for illustration.
1. Let all the four vertices v1, v2, v3, v4 be black and bad. Then the graph G consists of
a single cycle on four vertices, which is not a counterexample.
2. Let v1, v2, and v3 be black and bad. Then all the four edges of α are incident with the
same big face β and α is hanging on v4. Hence, β sends 3 units of charge to α (Rule
1). The face α then sends 3 · 2 units of charge to the 2-vertices v1, v2, v3 and at most
1 unit of charge to v4 (Rule 3). If the vertex v4 is a 3-vertex, the third edge incident
with it is a bridge in G. Therefore, deg(v4) ≥ 4 and v4 sends 2 units of charge to α
(Rules 4 – 6). The new charge of α is 2 + 3− 3 · 2− 1 + 2 = 0.
3. Let v1 and v3 be black and bad. Let β1 be the big face incident with v1, let β2 be the
big face incident with v3.
If β1 6= β2, both β1 and β2 send 3 units of charge to α. The face α then sends 2 units
of charge to the vertices v1 and v3 and at most 1 unit of charge to the vertices v2 and
v4. The new charge of α is at least 2 + 2 · 3− 2 · 2− 2 · 1 = 2. If β1 = β2, then v2
and v4 are not blue, and the new charge of α is at least 2 + 3− 2 · 2 = 1.
266 Ars Math. Contemp. 4 (2011) 255–269
4. Let v1 and v2 be black and bad. Let β1 be the big face incident with the edge v3v4
and β2 be the big face incident with the vertices v1 and v2. If β1 6= β2, β2 sends 3
units of charge to α and β1 sends at least 1 unit of charge to α. The face α then sends
2 units of charge both to v1 and v2 and at most 1 unit of charge to v3 and v4. The
new charge of α is at least 2 + 3 + 1− 2 · 2− 2 · 1 = 0. If β1 = β2, then v3 and v4
are not blue, and the new charge of α is at least 2 + 3− 2 · 2 = 1.
5. Let v1 be black and bad. The big face β1 incident with v1 sends 3 units of charge
to α. The face α then sends 2 units of charge to v1 and at most 1 unit of charge to
v2, v3, and v4. The new charge of α is at least 2 + 3− 2− 3 · 1 = 0.
6. Let no black and bad vertex be incident with α. Then the big faces adjacent to α
send together at least 2 units of charge (if there was only one big face, it would send
3 units of charge), and α sends at most 1 unit of charge to each incident vertex. The
new charge of α is at least 2 + 2− 4 = 0.
v1 v2
v3v4
α
β
v1
v2
v3
v4
α
β1
β2
v1
v2
v3
v4
α
β2
β1
v1
v2
v3
v4
α
β1
v1
v2
v3
v4
α
Figure 10: Different possible neighbourhoods of a 4-face α.
3.3.6 5-faces
Let α be a 5-face. Its initial charge is 4. Let v1, v2, v3, v4, v5 be the vertices incident with
α. (They do not have to be pairwise different.) Consider the number of black vertices bad
for α. Note that by Claim 3.11 each such vertex is either a 2-vertex or a 4-vertex with a
hanging 1-face. See Figure 11 for illustration.
1. Let all the five vertices v1, v2, v3, v4, v5 be black and bad. Then the graphG contains
only 5 vertices, hence, it is not a counterexample.
2. Let v1, v2, v3, and v4 be black and bad. From Claim 3.6 it follows that none of them
is incident with a 1-face. Then all the five edges of α are incident with the same big
face β and α is hanging on v5. Hence, β sends 3 units of charge to α (Rule 1). The
face α then sends 4 · 2 units of charge to the 2-vertices v1, v2, v3, and v4 (Rule 3) and
at most 1 unit of charge to the vertex v5 (Rule 3). If the vertex v5 is a 3-vertex, the
third edge incident with it is a bridge in G. Therefore deg(v5) ≥ 4 and v5 sends 2
units of charge to α (Rules 4 – 6). The new charge of α is 4 + 3− 4 · 2− 1 + 2 = 0.
3. Let v1, v2, and v3 be black and bad. Let β1 be the big face incident with the vertices
v1, v2, and v3 and β2 be the big face incident with the edge v4v5. By Claim 3.12
v1, v2, and v3 are 2-vertices. If β1 6= β2, β1 sends 3 units of charge to α and β2
sends at least 1 unit of charge to α. The face α then sends 2 units of charge to v1, v2,
and v3 and at most 1 unit of charge to v4 and v5. The new charge of α is at least
4 + 3 + 1− 3 · 2− 2 · 1 = 0. If β1 = β2, then v4 and v5 are not blue, and the new
charge of α is at least 4 + 3− 3 · 2 = 1.
J. Czap, S. Jendrol’and F. Kardoš: Facial parity edge colouring 267
4. Let v1, v2, and v4 be black and bad. Let β1 be the big face incident with v1 and v2,
let β2 be the big face incident with v4. By Claim 3.12 v1 and v2 are 2-vertices, thus
β1 sends 3 units of charge to α.
If β1 6= β2, then β2 sends at least 1 unit of charge to α. The face α then sends 2 units
of charge to the vertices v1, v2, and v4 and at most 1 unit of charge to the vertices v3
and v5. The new charge of α is at least 4 + 3 + 1− 3 · 2− 2 · 1 = 0. If β1 = β2, then
v3 and v5 are not blue, and the new charge of α is 4 + 3− 3 · 2 = 1.
5. Let v1 and v2 be black and bad. Let β1 be the big face incident with the vertices v1
and v2. The face β1 sends 3 units of charge to α. The face α then sends 2 units of
charge both to v1 and v2 and at most 1 unit of charge to v3, v4, and v5. The new
charge of α is at least 4 + 3− 2 · 2− 3 · 1 = 0.
6. Let v1 and v3 be black and bad. Let β1 be the big face incident with v1, β2 be the big
face incident with v3, and β3 be the big face incident with the edge v4v5. If β1, β2,
and β3 are three different faces, the new charge of α is at least 4+3−2 ·2−3 ·1 = 0.
If two of them coincide, then at least one of the vertices v2, v4, and v5 is not blue and
the new charge of α is at least 4 + 2− 2 · 2− 2 · 1 = 0. If β1 = β2 = β3, then v2, v4,
and v5 are not blue and the new charge of α is at least 4 + 1− 2 · 2 = 1.
7. Let v1 be black and bad. Then the big faces adjacent to α send together at least 2
units of charge (if there was only one big face, it would send 3 units of charge). The
new charge of α is at least 4 + 2− 2− 4 · 1 = 0.
8. Let no black and bad vertex be incident with α. Then the big faces adjacent to α send
together at least 1 unit of charge. The new charge of α is at least 4 + 1− 5 = 0.
α
v1
v2
v3v4
v5
β
α
v1
v2
v3v4
v5
β1
β2
α
v1
v2
v3v4
v5
β2
β1
α
v1
v2
v3v4
v5
β1
α
v1
v2
v3v4
v5
β3 β2
β1
α
v1
v2
v3v4
v5 α
v1
v2
v3v4
v5
Figure 11: Different possible neighbourhoods of a 5-face α.
3.3.7 Small faces of size at least 6
Let α be a d-face, 6 ≤ d ≤ 44. Its initial charge is 2d − 6. Let v1, . . . , vd be the vertices
incident with α. (They do not have to be pairwise different.) Consider the black vertices
incident with α. Let vi be a black 4-vertex. It cannot be good for α, since no two small
faces are adjacent (see Claim 3.5). Therefore, each black 4-vertex is bad for α. By Claim
3.10 at most d− 2 vertices incident with α are bad. Let k ≤ d− 2 be the number of black
vertices incident with α. We can divide the facial walk of α into d − k ≥ 2 parts, each
beginning and ending in a blue or white vertex, each incident with α and a big face βi,
268 Ars Math. Contemp. 4 (2011) 255–269
i ∈ {1, . . . , d− k}. Each of these big faces sends at least 1 unit of charge to α. (If βi = βj
for some 1 ≤ i < j ≤ d − k, the face βi cannot be adjacent to another small face but α,
therefore, it sends 3 units to α, which is even more than what two different big faces would
send.)
The face α then sends 2 units of charge to each of the k incident black vertices, and at
most 1 unit of charge to each of the other incident vertices. Together, the new charge of α
is at least
2d− 6 + (d− k) · 1− k · 2− (d− k) · 1 = 2(d− k)− 6.
If d− k ≥ 3, the new charge of α is non-negative.
Let d− k = 2. It means there are only two vertices which are not black. Since d ≥ 6,
at least one big face β shares at least 2 black vertices with α, say v1 and v2. By Claim 3.10
at least one from v1 and v2 is a 2-vertex, hence, by Claim 3.14 the face β sends 3 units of
charge to α. The new charge of α is therefore at least
2d− 6 + 3 + 1− (d− 2) · 2− 2 · 1 = 0.
3.3.8 Big faces
Let β be a d-face, d ≥ 45. Its initial charge is 2d− 6. It sends 3 units of charge to the small
faces it is adjacent to (Rule 1). It sends 2 units of charge to all bad black vertices; 1 unit
of charge to all other vertices. Let k be the number of black vertices bad for β. By Claim
3.10, k ≤ 45 · d. The new charge of β is therefore at least
2d− 6− 3− k · 2− (d− k) · 1 = d− k − 9 ≥ d− 4d
5
− 9 = d
5
− 9 = d− 45
5
≥ 0.
The new charge of all elements of the graph is non-negative, but the sum of all the
charges is −12, which is a contradiction. This contradiction implies that the minimum
counterexample does not exist.
Acknowledgments
This work was supported by Slovak Research and Development Agency under contract
No. APVV-0007-07. Support of Slovak VEGA Grant 1/0428/10 is acknowledged as well.
Institute for Theoretical Computer Science (ITI) is supported by Ministry of Education of
the Czech Republic as project 1M0545.
The authors thank the referees for many helpful comments and suggestions.
References
[1] D. P. Bunde, K. Milans, D. B. West and H. Wu, Optimal strong parity edge-coloring of complete
graphs, Combinatorica 28 (2008), 625–632.
[2] D. P. Bunde, K. Milans, D. B. West and H. Wu, Parity and strong parity edge-coloring of graphs,
Congressus Numerantium 187 (2007), 193–213.
[3] J. Czap and S. Jendrol’, Colouring vertices of plane graphs under restrictions given by faces,
Discussiones Math. Graph Theory 29 (2009), 521–543.
[4] T. Mátrai, Covering the edges of a graph by three odd subgraphs, J. Graph Theory 53 (2006),
75–82.
J. Czap, S. Jendrol’and F. Kardoš: Facial parity edge colouring 269
[5] L. Pyber, Covering the edges of a graph by . . . , Sets, Graphs and Numbers, Colloquia Mathe-
matica Societatis János Bolyai 60 (1991), 583–610.
[6] V. G. Vizing, On an estimate of the chromatic class of a p-graph, Diskret. Analiz 3 (1964),
25–30.