Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 289–293
Facial parity edge coloring of outerplane graphs
Július Czap
Department of Applied Mathematics and Business Informatics, Faculty of Economics,
Technical University of Košice, Němcovej 32, 040 01 Košice, Slovakia
Received 6 September 2011, accepted 1 December 2011, published online 28 March 2012
Abstract
A facial parity edge coloring of a 2-edge-connected plane graph is such an edge
coloring in which no two face-adjacent edges (consecutive edges of a facial walk of some
face) receive the same color, in addition, for each face f and each color c, either no edge
or an odd number of edges incident with f is colored with c. It is known that any 2-edge-
connected plane graph has a facial parity edge coloring with at most 92 colors. In this paper
we prove that any 2-edge-connected outerplane graph has a facial parity edge coloring with
at most 15 colors. If a 2-edge-connected outerplane graph does not contain any inner edge,
then 10 colors are sufficient. Moreover, this bound is tight.
Keywords: Plane graph, facial walk, edge coloring.
Math. Subj. Class.: 05C10, 05C15
1 Introduction
The facial parity edge coloring concept was introduced in [4]. The motivation has come
from the papers of Bunde et al. [1, 2]. They introduced parity edge colorings of graphs. A
parity walk in an edge coloring of a simple graph is a walk along which each color is used
an even number of times. Let p(G) be the minimum number of colors in an edge coloring
of G having no parity path (parity edge coloring). Let p̂(G) be the minimum number of
colors in an edge coloring of G in which every parity walk is closed (strong parity edge
coloring). Clearly, every parity edge coloring is a proper edge coloring. Although there
are graphs G with p̂(G) > p(G) [1], it remains unknown how large p̂(G) can be when
p(G) = k. In [1] it is mentioned that computing p(G) or p̂(G) is NP-hard even when G is
a tree.
The facial parity edge coloring can be considered as a relaxation of the parity edge
coloring. We focus on facial cycles of plane graphs. This coloring has to satisfy the
following two conditions:
E-mail address: julius.czap@tuke.sk (Július Czap)
Copyright c© 2012 DMFA Slovenije
290 Ars Math. Contemp. 5 (2012) 289–293
1. face-adjacent edges receive different colors,
2. for every color c and every face f the total number of occurrences of edges colored
with c on a facial walk of f is odd or zero.
The authors of [4] proved that every 2-edge-connected plane graph has a facial parity
edge coloring with at most 92 colors.
In this paper we substantially improve this bound for the class of 2-edge-connected
outerplane graphs.
Note that the vertex version of this problem was investigated in [5]. The authors proved
that every 2-connected plane graph admits a parity vertex coloring using at most 118 colors.
Kaiser et al. [8] improved this bound to 97. Czap [3] proved that any 2-connected outerplane
graph has such a coloring with at most 12 colors. The generalization of the parity coloring
for graphs and set systems can be found in [6].
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.
Outerplane graphs are plane graphs such that every vertex lies on the outer face.
A bridge is an edge whose removal increases the number of components. A graph
which contains no bridge is said to be bridgeless or 2-edge-connected. In this paper we
consider connected bridgeless plane graphs, multiple edges and loops are allowed.
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 consists of replacing u and v by a new vertex adjacent to all
the former neighbors of u and v, and removing the loop corresponding to the edge e. (We
keep multiple edges if they arise.)
Two (distinct) edges are face-adjacent if they are consecutive edges of a facial walk of
some face f .
A k-edge coloring of a graph G = (V,E) is a mapping ϕ : E(G) → {1, . . . , k}. We
say that an edge coloring of a plane graphG is facially proper if no two face-adjacent edges
of G receive the same color. The facial parity edge coloring of a 2-edge-connected plane
graph is a facially proper edge coloring such that for each face f and each color c, either
no edge or an odd number of edges incident with f is colored with c.
Question 2.1. What is the minimum number of colors χ′p(G) such that a 2-edge-connected
plane graph G has a facial parity edge coloring with at most χ′p(G) colors?
3 Results
Lemma 3.1. Let Cn be a cycle on n edges, n ≥ 1. Then χ′p(Cn) ≤ 5.
Proof. If n = 1, then we use one color. Let n = 4k + z, where k is a non-negative integer
and z ∈ {2, 3, 4, 5}. We repeat k times the pattern 1, 2, 1, 2 and then use colors 1, 2, . . . , z.
The colors 1 and 2 are thus used 2k + 1 times, the remaining three colors are used at most
once.
An edge of a plane graph not incident with the outer face is called inner edge.
Theorem 3.2. LetG be a 2-edge-connected outerplane graph with no inner edge (bridgeless
cactus graph). Then χ′p(G) ≤ 10. Moreover, this bound is tight.
J. Czap: Facial parity edge coloring of outerplane graphs 291
Proof. First we prove that the edges of G can be colored with at most 5 colors, say
1, 2, 3, 4, 5, in such a way that for every inner face f and every color c ∈ {1, 2, 3, 4, 5},
either no edge or an odd number of edges incident with f is colored with c, in addition,
face-adjacent edges receive different colors.
The proof is by induction on the number of inner faces. If G has one inner face, then
the statement follows from Lemma 3.1. Let G have k inner faces f1, . . . , fk and assume
that the face fk is such a face of G that the corresponding vertex in a block graph of G is a
leaf. Let H be a subgraph of G consisting of faces f1, . . . , fk−1. The graph H has fewer
inner faces than G, hence it has a required coloring. It is easy to extend the coloring of H
to a coloring of G. Assume that the boundary of fk is a cycle C. Clearly, C and H have
exactly one vertex v in common. There are at most two forbidden colors for the edges of
C incident with v. We have five colors, hence there is such a facial parity edge coloring of
the cycle C that no two face-adjacent edges incident with v receive the same color in G.
In the next step we recolor some edges. Assume that a color i ∈ {1, 2, 3, 4, 5} appears
an even number of times in G. Let f be an arbitrary inner face which is incident with an
edge of color i. We recolor all the edges of color i incident with f with a new color i+ 5.
Now the total number of occurrences of edges colored with i and i+ 5 is odd in G.
This recoloring uses at most 10 colors.
To see that the upper bound is tight it is sufficient to consider the graph in Figure 1.
Figure 1: An example of a graph with no facial parity edge coloring using less than 10
colors.
Corollary 3.3. LetG be a bridgeless cactus graph with noC5. Thenχ′p(G) ≤ 8. Moreover,
this bound is tight.
Proof. First we show that among all cycles only the cycle on five edges requires 5 colors
for a facial parity edge coloring. Let n = 4k + z, where k is a non-negative integer
and z ∈ {2, 3, 4, 5}. If z 6= 5, then χ′p(Cn) ≤ 4 (see the proof of Lemma 3.1). If
n = 4k + 5, k ≥ 1, then χ′p(Cn) = 3 (we repeat the pattern 1, 2, 3 three times and then
repeat k − 1 times the pattern 1, 2, 1, 2).
Now we can proceed as in the proof of Theorem 3.2.
Corollary 3.4. Let G be a bridgeless cactus graph with no C5 and no C4k, k ≥ 1. Then
χ′p(G) ≤ 6. Moreover, this bound is tight.
The dual G∗ of a plane graph G can be obtained as follows: Corresponding to each
face f of G there is a vertex f∗ of G∗, and corresponding to each edge e of G there is an
edge e∗ of G∗; two vertices f∗ and g∗ are joined by the edge e∗ in G∗ if and only if their
corresponding faces f and g are separated by the edge e in G (an edge separates the faces
incident with it). The weak dual of a plane graph G is the subgraph of the dual graph G∗
whose vertices correspond to the bounded faces of G.
292 Ars Math. Contemp. 5 (2012) 289–293
Lemma 3.5. [7] The weak dual of an outerplane graph is a forest.
We say that an edge coloring of a graph is odd, if each color class induces an odd
subgraph (each vertex has an odd degree).
Lemma 3.6. Let Sn be a star on n edges, n ≥ 1. Then it has a facially proper odd edge
coloring using at most 5 colors.
Proof. We can use the coloring defined in the proof of Lemma 3.1.
Corollary 3.7. Let T be a tree. Then it has a facially proper odd edge coloring using at
most 5 colors.
Proof. Pick any vertex of T to be the root. We color the edges of T starting from the root
to the leaves. In each step it is sufficient to find a facially proper odd edge coloring of a star
with (at most) one precolored edge.
Corollary 3.8. Let F be a forest. Then it has a facially proper odd edge coloring using at
most 5 colors.
Theorem 3.9. Let G be a 2-edge-connected outerplane graph. Then χ′p(G) ≤ 15.
Proof. First we color all the edges on the outer face with yellow color. The other edges let
be green.
We successively contract the green edges and we obtain a graph H . The graph H is
outerplane with no inner edge, hence, from Theorem 3.2 it follows that there exists a facial
parity edge coloring of H with at most 10 colors.
In the following we extend the coloring ofH to a coloring ofG. Let F be the weak dual
of G. Lemma 3.5 implies that F is a forest. By Corollary 3.8, F has a facially proper odd
edge coloring which uses at most 5 colors. This coloring induces a coloring of the green
edges of G in a natural way. The coloring of the yellow edges with at most 10 colors and
the coloring of the green edges with at most 5 colors (these five colors are different than the
previous ten ones) induce a required coloring of G.
Acknowledgments
I would like to thank one of the anonymous referees for helpful comments and suggestions.
References
[1] 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.
[2] D. P. Bunde, K. Milans, D. B. West and H. Wu, Optimal strong parity edge-coloring of complete
graphs, Combinatorica 28 (2008), 625–632.
[3] J. Czap, Parity vertex coloring of outerplane graphs, Discrete Math. 311 (2011), 2570–2573.
[4] J. Czap, S. Jendrol’ and F. Kardoš, Facial parity edge colouring, Ars Math. Contemp. 4 (2011),
255–269.
[5] J. Czap, S. Jendrol’ and M. Voigt, Parity vertex colouring of plane graphs, Discrete Math. 311
(2011), 512–520.
[6] J. Czap and Zs. Tuza, Partitions of graphs and set systems under parity constraints, preprint,
2011.
J. Czap: Facial parity edge coloring of outerplane graphs 293
[7] H. J. Fleischner, D. P. Geller and F. Harary, Outerplanar graphs and weak duals, J. Indian Math.
Soc. 38 (1974), 215–219.
[8] T. Kaiser, O. Rucký, M. Stehlı́k and R. Škrekovski, Strong parity vertex coloring of plane graphs,
IMFM Preprint series 49 (2011), #1144.