Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 165–175
3-Connected planar graphs are 5-distinguishing
colorable with two exceptions∗
Gašper Fijavž
Faculty of Computer and Information Science, University of Ljubljana
Tržaška 25, 1000 Ljubljana, Slovenia.
Seiya Negami
Faculty of Education and Human Sciences, Yokohama National University
79-2 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan.
Terukazu Sano
Graduate School of Environment and Information Sciences, Yokohama National
University, 79-7 Tokiwadai, Hodogaya-Ku, Yokohama 240-8501, Japan.
Received 31 March 2010, accepted 23 January 2011, published online 19 March 2011
Abstract
A graph G is said to be d-distinguishing colorable if there is a d-coloring of G such
that no automorphism of G except the identity map preserves colors. We shall prove that
every 3-connected planar graph is 5-distinguishing colorable except K2,2,2 and C6 + K2
and that every 3-connected bipartite planar graph is 3-distinguishing colorable except Q3
and R(Q3).
Keywords: planar graphs, distinguishing number, distinguishing chromatic number.
Math. Subj. Class.: 05C15, 05C10
1 Introduction
A coloring or a k-coloring of a graph G is an assignment of k colors to its vertices so
that every pair of adjacent vertices gets different colors and the chromatic number χ(G) of
G is defined as the minimum number k such that G admits a k-coloring, as usual. Even
if a graph itself has rich symmetry, its coloring does not adapt to symmetry in general
∗Dedicated to the memory of Michael Albertson.
E-mail addresses: gasper.fijavz@fri.uni-lj.si (Gašper Fijavž), negami@edhs.ynu.ac.jp (Seiya Negami),
d08tc004@ynu.ac.jp (Terukazu Sano)
Copyright c© 2011 DMFA Slovenije
166 Ars Math. Contemp. 4 (2011) 165–175
and it might become completely asymmetric. How many colors do we need to break the
symmetry of a graph? We formulate this consideration as follows.
Let c : V (G) → {1, . . . , k} be a coloring of a graph G. We denote by Aut(G, c) the
set of automorphisms σ over G that preserve the colors given by c.
Aut(G, c) = {σ ∈ Aut(G) : c(σ(v)) = c(v) for all v ∈ V (G)}
It is clear that Aut(G, c) forms a subgroup in the automorphism group Aut(G) of G. If
Aut(G, c) is trivial, that is, if it includes only the identity map idG, then c is said to be
distinguishing or is called a k-distinguishing coloring involving the number of colors k. If
G admits a k-distinguishing coloring, then G is said to be k-distinguishing colorable. The
distinguishing chromatic number of G is defined as the minimum number k such that G is
k-distinguishing colorable and is denoted by χD(G).
A planar graph is one that can be drawn in the plane without crossings on edges. It
is well-known that every planar graph is 4-colorable, by the “Four Color Theorem”, that
is, the chromatic number of planar graphs is bounded by 4. We would like to establish a
similar theorem for the distinguishing chromatic number of planar graphs. However, there
is no finite upper bound for it; it is easy to see that χD(K2,n) = n + 2 for example.
Thus, we need some assumption on graphs to bound the distinguishing chromatic number
in general.
A graph is said to be n-connected if it has at least n+ 1 vertices and if removing fewer
than n vertices does not disconnect it. Recently, Negami and Sakurai [6] have proved the
following theorem on planar graphs as an application of general arguments on the distin-
guishing chromatic number of graphs faithfully embedded on closed surfaces; we shall
explain later the faithfulness of embedding.
Theorem 1.1 (Negami and Sakurai [6]). Every 3-connected planar graph is 6-distinguish-
ing colorable.
This theorem is best possible in two meanings. First, the assumption of being 3-
connected cannot be omitted. For example, K2,n is not 3-connected and its distinguish-
ing chromatic number can be arbitrarily large, as mentioned above. Secondly, there exist
3-connected planar graphs that are not 5-distinguishing colorable, as follows.
Let Cn + K2 denote the suspension over a cycle Cn of length n, that is, Cn with two
extra vertices adjacent to all vertices along Cn. This may be called a double wheel with rim
Cn. In particular, C4 + K2 is isomorphic to K2,2,2, which is the octahedron. The double
wheels are 5-distinguishing colorable except two; χD(K2,2,2) = χD(C6 +K2) = 6. They
are 3-connected and can be embedded on the sphere as a triangulation, that is, so that each
face is triangular. A graph having such an embedding is said to be maximal planar in
general and adding any new edge to it results in a nonplanar graph.
Negami and Sakurai [6] have proved that every maximal planar graph is 5-distinguish-
ing colorable if it is isomorphic to neither of these two exceptions and conjectured that
every 3-connected planar graph is 5-distinguishing colorable with a finite number of ex-
ceptions. In this paper, we shall solve their conjecture affirmatively and show that the
exceptions are the two listed above:
Theorem 1.2. Every 3-connected planar graph is 5-distinguishing colorable unless it is
isomorphic to either K2,2,2 or C6 +K2.
G. Fijavž et al.: 3-Connected planar graphs are 5-distinguishing colorable. . . 167
It has been shown in [6] that χD(Cn + K2) = 5 if n 6= 4, 6 and hence we cannot
improve the above theorem even if we allow a finite number of exceptions. However, there
are many planar graphs whose distinguishing chromatic number is less than 5. For example,
it is not so difficult to show that every 3-connected bipartite planar graph is 4-distinguishing
colorable. We shall prove a stronger fact on bipartite planar graphs. In general, the radial
graph R(G) of a graph G embedded on the sphere is defined as the graph obtained as
follows; put a vertex in each face of G, join it to all vertices lying along the boundary cycle
of the face, and finally delete all original edges of G:
Theorem 1.3. Every 3-connected bipartite planar graph is 3-distinguishing colorable un-
less it is isomorphic to either the 3-cube Q3 or its radial graph R(Q3).
The distinguishing chromatic number of graphs has been introduced in [3], as a variant
of the distinguishing number. The latter can be defined in the same way as for the former
without the assumption of c being a proper coloring in the previous; c is just an assignment
of numbers to vertices and adjacent vertices may have the same number. There have been
a lot of studies about the distinguishing number of graphs, see [1, 2, 4].
2 General case
The point of our arguments below is the fact that a 3-connected planar graph can be embed-
ded on the sphere so that any automorphism σ of G extends to an auto-homeomorphism
h over the sphere with h|G = σ. Such an embedding is said to be faithful. The notion
of faithful embeddings has been introduced in [5] and the faithfulness of an embedding of
any 3-connected planar graph on the sphere can be derived from the uniqueness of its dual,
proved by Whitney [8].
To conclude that a given graph is k-distinguishing colorable, we must show that every
automorphism σ ∈ Aut(G, c) is the identity map for a suitable k-coloring of G. The
following lemma has been proved and used to do it in [4, 6] and also we shall often use it
implicitly.
Lemma 2.1. Let G be a 3-connected planar graph embedded on the sphere and σ its
automorphism. If σ fixes all vertices lying along the boundary cycle of a face, then σ is the
identity map.
As is mentioned in the Introduction, Theorem 1.2 has been proved in the case of max-
imal planar graphs in [6]. However, we shall include our own arguments for such a case
in the proof below to make it self-contained. An n-cut in a connected graph is a set of n
vertices whose removal results in a disconnected graph. The following lemma is useful to
discuss the distinguishing chromatic number of triangulations:
Lemma 2.2. If a triangulation G on the sphere has a 3-cut, then χD(G) ≤ χ(G) + 1.
Proof. In general, the three vertices of any 3-cut in a triangulationG form a cycle of length
3 and it separates the vertices of G into two groups. Call such a cycle a separating 3-
cycle here. If G is embedded on the plane, we can distinguish the inside and outside of a
separating 3-cycle and can consider an innermost separating 3-cycle, that is, one such that
its inside contains no other separating 3-cycles.
Let C = v1v2v3 be an innermost separating 3-cycle of G and choose a vertex x inside
C. Consider a k-coloring c̄ : V (G) → {1, . . . , k} of G with c̄(vi) = i for i = 1, 2, 3 and
168 Ars Math. Contemp. 4 (2011) 165–175
change the color of x to k+1 to obtain a (k+1)-coloring c ofG. Clearly, any automorphism
σ ∈ Aut(G, c) fixes x and cannot move C into its inside since it is innermost. This implies
that σ(C) = C and hence σ fixes each of v1, v2 and v3 since they have different colors.
Consider another triangulation G′ obtained from G by deleting all vertices lying in the
inside of C. Then the region inside C is a face of G′ with boundary cycle C and σ induces
naturally an automorphism σ′ of G′ such that it fixes the face. Applying Lemma 2.1 to σ′,
we conclude that σ′ is the identity map of G′ and hence σ is the identity map of G since σ
fixes the faces outside C. Therefore, G is (k + 1)-distinguishing colorable.
The neighbors of a vertex in a triangulation G on a closed surface form a cycle and
such a cycle is called its link. If a triangulation G on the sphere has a vertex of degree 3,
then the link of the vertex becomes a separating 3-cycle of G and G is not 4-connected.
If a triangulation G on the sphere is not 4-connected in general, then we have χD(G) ≤
χ(G) + 1 by Lemma 2.2 and hence G is 5-distinguishing colorable since χ(G) ≤ 4 by
Four Color Theorem.
Let G be a 3-connected graph embedded on the plane or on the sphere. Then each
face of G is bounded by a cycle. The size of a face A in G is defined as the length of the
boundary cycle of A and is denoted by |A|. We call a face A an even face or an odd face
below, according to the parity of |A|.
Here we shall prove Theorem 1.2, that is, show that every 3-connected planar graph is
5-distinguishing colorable, specifying the two exceptions.
Proof of Theorem 1.2. LetG be a 3-connected planar graph and suppose that it is faithfully
embedded on the sphere. By Four Color Theorem, G has a coloring c̄ with at most four
colors. We shall modify it to a 5-distinguishing coloring c in each of the following cases.
CASE 1. There is no odd face: In this case, G is a bipartite planar graph and hence it
has a 2-coloring c̄ : V (G) → {1, 2}. We can find four distinct vertices x1, y1, x2 and y2
so that x1y1x2 and y1x2y2 form corners of two faces sharing an edge y1x2, that is, they
are paths of length 2 lying along the boundary cycles of the faces. Consider a 4-coloring
c of G defined by c(x1) = c(x2) = 3, c(y1) = c(y2) = 4 and c(v) = c̄(v) for the other
vertices v. It is clear that any automorphism σ ∈ Aut(G, c) fixes the two corners x1y1x2
and y1x2y2 and σ is the identity map. Therefore, c is a 4-distinguishing coloring and hence
χD(G) ≤ 4 in this case.
CASE 2. There is an odd face of size at least 5: Consider a 4-coloring c̄ : V (G) →
{1, 2, 3, 4} of G. Let A be an odd face of G with |A| = 2m+ 1 ≥ 5 and C = v0v1 · · · v2m
its boundary cycle. Define a 5-coloring c of G by c(v1) = c(v2m) = 5 and c(w) = c̄(w)
for the other vertices w. Take any automorphism σ ∈ Aut(G, c) with its extension h over
the sphere. If h(A) 6= A, then the two faces h(A) and A meet each other in {v1, v2m},
which would form a 2-cut of G, contrary to G being 3-connected. Therefore, we conclude
that h(A) = A and hence σ(C) = C.
It is clear that there are two possibilities on σ; it acts on C as either the identity map
or the reflexion exchanging v1 and v2m. If the latter happened, then σ would exchange
vm and vm+1, but this is impossible since they have different colors. Therefore, σ is the
identity map and hence c is a 5-distinguishing coloring of G.
CASE 3. There exist odd faces and even faces, and all odd faces are of size 3: In this case,
we can find two faces A and B with |A| = 3 and |B| ≥ 4 so that they share an edge xy.
G. Fijavž et al.: 3-Connected planar graphs are 5-distinguishing colorable. . . 169
Consider the graph G/xy obtained from G by contracting xy. Since G/xy might contain
multiple edges but no self-loop, we can consider a coloring ofG/xy. SinceG/xy is planar,
G/xy admits a 4-coloring and it induces a color assignment c′ ofGwith c′(x) = c′(y) = 4;
this c′ is not a proper coloring of G. Define a 5-coloring c : V (G) → {1, 2, 3, 4, 5} of G
by c(y) = 5 and c(w) = c′(w) for the other vertices w. Since the neighbors of y except x
do not get color 4 in c, the edge xy is a unique one which joins colors 4 and 5. Thus, any
automorphism σ ∈ Aut(G, c) fixes x and y. Furthermore, σ fixesA andB since |A| 6= |B|
and hence it is the identity map by Lemma 2.1. This implies that c is a 5-distinguishing
coloring of G.
CASE 4. All faces are of size 3: If the three previous cases do not happen, then there
is no even face and all faces are triangular. Thus, this case is the final one that we have to
discuss. Now G is a maximal planar graph embedded on the sphere as a triangulation. We
may assume that G is 4-connected by Lemma 2.2.
First suppose that G has a vertex v of degree d = 5 or ≥ 7 and let C = v0v1 · · · vd−1
be the link around v. If there exists an edge vivi+3 in G, with indices taken modulo d,
then {v, vi, vi+3} would form a 3-cut, contrary to G being 4-connected. Thus we may
assume that there is no such edge in G. Consider a 4-coloring c̄ of G. Then we can
define a 5-coloring ci : V (G) → {1, 2, 3, 4, 5} of G for each i ∈ {0, 1, . . . , d − 1} by
ci(vi) = ci(vi+3) = 5 and ci(w) = c̄(w) for the other vertices w since there is no edge
between vi and vi+3.
If any automorphism σ ∈ Aut(G, ci) fixes v, then it fixes C and we conclude that σ
fixes each vertex lying along the link of v. For, the two vertices with color 5 cut C into two
segments of length 3 and d − 3 (6= 3). Since they have different lengths, σ cannot swap
them. Since c(vi+1) 6= c(vi+2), σ cannot flip the segment vivi+1vi+2vi+3, exchanging
vi and vi+3 and hence it fixes C. Thus, ci is a 5-distinguishing coloring of G in this case.
Otherwise, there is an automorphism σi ∈ Aut(G, ci) with σi(v) 6= v and σi(v) is adjacent
to both vi and vi+3. If this happens for all i, then we find d vertices σi(v) outside the link
of v such that the cycle vviσi(v)vi+3 separates vi+1 and vi+2 from the rest. The planarity
forces all σi(v)’s to be one vertex, and G is isomorphic to Cd + K2. It is not difficult to
see that Cd +K2 for d = 5 or ≥7 is 5-distinguishing colorable and so is G.
Now we may suppose that every vertex in G has degree at most 6 and not equal to
5. Since G is 4-connected, all vertices of G have degree 4 or 6 and G has a 3-coloring
c̄ : V (G) → {1, 2, 3}; in general, a maximal planar graph is 3-colorable if and only if all
vertices have even degree.
Let v be one of vertices of degree 6, if any, with link C = v0v1v2v3v4v5. Since G is
4-connected, there is no edge between vi and vi+3 for all i and we can define a 5-coloring
ci : V (G)→ {1, 2, 3, 4, 5} of G by ci(vi) = ci(vi+3) = 4, ci(vi+1) = 5 and c(w) = c̄(w)
for the other vertices w. If any automorphism σ ∈ Aut(G, ci) fixes v, then we conclude
that ci is a 5-distinguishing coloring of G by the asymmetric coloring along C. Otherwise,
there is an automorphism σi ∈ Aut(G, ci) such that σi(v) lies outside C and is adjacent to
all of vi, vi+1 and vi+3. If this happens for all i, then G is isomorphic to C6 + K2 by the
same logic as in the previous case.
On the other hand, if G has no vertex of degree 6, then all vertices have degree 4 and
we can conclude that G is isomorphic to K2,2,2, which is one of the exceptions.
Finally we have shown that G is 5-distinguishing colorable or is isomorphic to one of
the exceptions. Thus the theorem follows.
170 Ars Math. Contemp. 4 (2011) 165–175
NOTE 1: It is easy to show that a 3-connected planar graphG is 6-distinguishing colorable,
as follows. Suppose that G is faithfully embedded on the sphere and let uvw be a corner
of a face A of G. Contract the edge uv to a vertex [uv] and consider a 4-coloring c̄ of the
resulting graph G/uv with c̄([uv]) = 4. Using this, we can define a 6-coloring c of G by
c(u) = 4, c(v) = 5, c(w) = 6 and c(x) = c̄(x) for any vertex x other than u, v and w.
Then uv is a unique edge with colors 4 and 5 at its ends and A is a unique face having
a corner with colors 4, 5 and 6. These force any automorphism σ ∈ Aut(G, c) to be the
identity map. Therefore, c is a 6-distinguishing coloring.
This argument works to prove that χD(G) ≤ χ(G/uv) + 2 for a 3-connected planar
graph G. On the other hand, Negami and Sakurai’s proof of Theorem 1.1 concludes that
χD(G) ≤ χ(G) + 2 unless G is isomorphic to K2,2,2 or C6 + K2. However, we cannot
say which is better than the other. If G is bipartite, then the latter implies that χD(G) ≤ 4,
but the former does not; if uv lies on a cycle, then we have χ(G/uv) = 3. If G has an
odd cycle and all odd cycles contain uv, then G/uv is bipartite and the former implies that
χD(G) ≤ 4, but the latter does not.
NOTE 2: We can construct infinitely many 3-connected planar graphs G with χD(G) = 5,
different from the series of Cn + K2, as follows. Let G0 be the graph consisting of two
triangles uvw+0 and uvw
−
0 sharing an edge uv and another vertex x of degree 4 adjacent
to all of u, v, w+0 and w
−
0 . Then there is an automorphism σ0 of G0 which fixes u, v
and x, exchanging w+0 and w
−
0 . It is easy to see that G0 is 4-chromatic and has a unique
4-coloring, up to renaming colors. Add two extra vertices w+1 and w
−
1 to G0 so that w
+
1
(respectively w−1 ) is adjacent to u, v, w
+
0 (respectively w
−
0 ) in the resulting graph G1.
Then σ0 extends naturally to be an automorphism σ1 of G1 with σ1(w±1 ) = w
∓
1 and G1 is
uniquely 4-colorable as well as G0.
Similarly, we can construct a series of 3-connected planar graphs G0, G1, . . ., adding
vertices w+i and w
−
i to Gi−1 so that each of w
±
i is adjacent to three vertices which form
a triangle in Gi−1 and that Gi has an automorphism σi exchanging w+j and w
−
j for all
j ≤ i and fixing u, v and x. Then Gi is uniquely 4-colorable for all i. As evidenced
by the existence of σi, the unique 4-coloring of Gi is not a distinguishing coloring. This
implies that Gi is not 4-distinguishing colorable and hence χD(G) ≥ 5. Since Gi is 5-
distinguishing colorable by Theorem 1.2, we have χD(G) = 5.
3 Bipartite case
We have already discussed the distinguishing chromatic number of 3-connected bipar-
tite planar graphs in Case 1 in our proof of Theorem 1.2 and concluded that they are 4-
distinguishing colorable. This is a best possible result if we do not allow any exception:
Lemma 3.1. χD(Q3) = 4 and χD(R(Q3)) = 4.
Proof. Embed Q3 in the 3-space as a unit cube with vertices having coordinates (x, y, z)
(x, y, z ∈ {0, 1}) and let vxyz be the vertex placed at (x, y, z). To show that χD(Q3) ≥ 4,
let c : V (Q3)→ {1, 2, 3} be any 3-coloring. Then we may assume that color 1 is used for
at most two vertices since Q3 has eight vertices. There are three different 3-colorings, up
to symmetry; color 1 appears only at v000, or one more at v110 or at v111. Coloring of the
other vertices with 2 and 3 is uniquely determined and we find a non-trivial automorphism
preserving colors in each case. Thus, there is no 3-distinguishing coloring of Q3 and hence
χD(Q3) ≥ 4.
G. Fijavž et al.: 3-Connected planar graphs are 5-distinguishing colorable. . . 171
u
e
e
u
e
u
u
e







@
@
@
@
@
@
@
@
i i
i
i
u u u
u
ue e
e e
e e
e e
u




@
@
@
@
@
@
@
@




@
@




@
@




@
@
@
@i ii i
Figure 1: 4-Distinguishing colorings of Q3 and R(Q3)
Similarly, we can conclude that there is no 3-distinguishing coloring of R(Q3), as
follows. The radial graph R(Q3) consists of the eight vertices belonging to V (Q3) and
the six vertices corresponding to faces of Q3. Suppose that R(Q3) has a 3-distinguishing
coloring c : V (R(Q3))→ {1, 2, 3} and let c̄ be its restriction to the six vertices belonging
to V (R(Q3))− V (Q3). If c̄ uses only one color then the restriction of c to V (Q3) induces
a distinguishing coloring of Q3. This implies that c would use at least five colors for
R(Q3) since χD(Q3) ≥ 4. Thus, we may assume that c̄ uses at least two colors. It
should be noticed that three faces of Q3 meeting at one vertex contain at most two colors;
otherwise, the vertex would need the fourth color in c. Paying attention to this, we can
find six candidates for c̄, up to symmetry; one of them uses three colors and the other use
two colors. For each coloring c̄, we can find a plane in the 3-space dividing the cube into
halves and reflexing the coloring c. This is contrary to c being a 3-distinguishing coloring.
Therefore, we need at least four colors to construct a distinguishing coloring of R(Q3) and
hence χD(R(Q3)) ≥ 4.
By Case 1 in the proof of Theorem 1.2, we have known that a 3-connected bipartite pla-
nar graph has a 4-distinguishing coloring. For example, Figure 1 presents 4-distinguishing
colorings of Q3 and R(Q3). Therefore, we have χD(Q3) = χD(R(Q3)) = 4.
Now we shall prove Theorem 1.3, that is, show that every 3-connected bipartite graph
is 3-distinguishing colorable, except the two graphs given in the above lemma.
Proof of Theorem 1.3. Let G be a 3-connected bipartite planar graph with partite sets X
and Y and suppose that it is faithfully embedded on the sphere. We can define a 2-coloring
c̄ : V (G) → {1, 2} of G with c̄(x) = 1 for x ∈ X and c̄(y) = 2 for y ∈ Y and any
face of G is bounded by a cycle of even length. We shall consider suitable 3-colorings
c, c′, ci : V (G) → {1, 2, 3} many times, assigning color 3 to some specified vertices; the
vertices other than those are always assumed to have the same colors as in c̄.
CASE 1. G is not a quadrangulation on the sphere: Since G is 3-connected and bipartite,
its dual G∗ is a simple planar graph with all vertices having even degree and there is no
vertex of degree 2 in G∗. Since every planar graph has a vertex of degree at most 5, G∗
has at least one vertex of degree 4 and the face of G corresponding to this vertex of G∗ is
quadrilateral. Thus, we can find a pair of faces A and B0 sharing one edge with |A| ≥ 6
and |B0| = 4 since G is not a quadrangulation. Let C = v0 · · · vd−1 be the boundary cycle
172 Ars Math. Contemp. 4 (2011) 165–175
of A with d ≥ 6 and v0v1u0w0 that of B0. Define a 3-coloring c : V (G)→ {1, 2, 3} of G
by c(v0) = c(v2) = 3.
Take any automorphism σ ∈ Aut(G, c) and let h be its extension over the sphere. Then
we have σ({v0, v2}) = {v0, v2} since there is no vertex with color 3 other than v0 and v2.
If h(A) 6= A, then the two faces h(A) and A meet each other in {v0, v2}, which would
form a 2-cut of G, contrary to G being 3-connected. Therefore, we have h(A) = A and
σ(C) = C. It is clear that if σ is not the identity map, then σ acts on C as a reflecion
fixing v1 and exchanging v0 and v2. This implies that there is a quadrilateral face B1
with boundary cycle σ(v1)σ(v0)σ(w0)σ(u0) = v1v2u1w1. Repeat the same argument
inductively as follows.
Suppose that we have found a quadrilateral face Bi with boundary cycle vivi+1uiwi.
Then we redefine a 3-coloring c by c(vi) = c(vi+2) = 3. If Aut(G, c) contains only the
identity map, then we can conclude that this c is a 3-distinguishing coloring and hence G
is 3-distinguishing colorable. Otherwise, any automorphism σ ∈ Aut(G, c) acts on C as
a reflecion, fixing vi+1 and exchanging vi and vi+2, and we find another quadrilateral face
Bi+1 with boundary cycle σ(vi+1)σ(vi)σ(wi)σ(ui) = vi+1vi+2ui+1wi+1. Therefore, if
we have never concluded that G is 3-distinguishing colorable, we find a sequence of d
quadrilateral faces Bi with boundary cycles vivi+1uiwi for i ≡ 0, . . . , d− 1(mod d).
By the planarity, we find a non-adjacent pair {ui, vi+3} for some i, say i = 0, and can
define a 3-coloring c′ : V (G)→ {1, 2, 3} by c′(v0) = c′(u0) = c′(v3) = 3; v0 and v3 are
not adjacent since {v0, v3} would form a 2-cut of G otherwise. Take any automorphism
σ ∈ Aut(G, c′) with its extension h over the sphere. Since v0, u0 ∈ X and v3 ∈ Y , we
have σ({v0, u0}) = {v0, u0} and σ(v3) = v3.
First suppose that σ(v0) = v0 for any automorphism σ ∈ Aut(G, c′). Then σ leaves
{v0, u0} and {v0, v3} invariant, respectively. By the assumption of G being 3-connected,
we have h(A) = A and h(B0) = B0 and hence σ fixes the edge v0v1 that A and B share.
This implies that h fixes A and B pointwise and hence σ is the identity map. Therefore, c′
is a 3-distinguishing coloring in this case.
On the other hand, if σ(v0) = u0, then there is a face h(A) ( 6= A) of the same size as A
whose boundary cycle includes u0 and v3. This face blocks the adjacency between u1 and
v4. In this case, we can redefine the 3-coloring c′ so that c′(v1) = c′(u1) = c′(v4) = 3 and
the previous case will happen for i = 1 since the face corresponding to h(A) ( 6= A) cannot
exist. Therefore, c′ is a 3-distinguishing coloring, again.
CASE 2. G is a quadrangulation on the sphere: We shall show thatGmust be isomorphic
to either Q3 or R(Q3), assuming that G is not 3-distinguishing colorable. Let x be a vertex
of degree d ≥ 5 inG, if any, with neighbors y0, . . . , yd−1 lying around it in this cyclic order
and xyixiyi+1 the boundary cycles of d facesAi incident to x for i ≡ 0, . . . , d−1(mod d).
We define a 3-coloring ci : V (G) → {1, 2, 3} by ci(yi) = ci(yi+1) = ci(xi+2) = 3 if
neither edge yixi+2 nor yi+1xi+2 exists.
First suppose that there is an edge between y0 and x2. Then neither edge y1x3 nor
y2x3 exists and we can define the 3-coloring c1. It is easy to see that an automorphism
σ ∈ Aut(G, c1) is the identity map if σ fixes x. Thus, there is an automorphism σ1 ∈
Aut(G, c1) with σ1(x) 6= x sinceG is assumed not to be 3-distinguishing colorable. Let h1
be the extension of σ1 over the sphere. Since σ1({y1, y2}) = {y1, y2}, we have σ1(x) = x1
and there is a face h1(A3) incident to both x1 and x3. However, the edge y0x2 blocks the
existence of such a face. Thus, this is not the case and we may assume that there is no edge
between yi and xi+2 for all i.
G. Fijavž et al.: 3-Connected planar graphs are 5-distinguishing colorable. . . 173
If there is an edge between y1 and x2, then neither edge yd−1x1 nor y0x1 exists and
we can define the 3-coloring cd−1. Since G is not 3-distinguishing colorable, there is an
automorphism σ ∈ Aut(G, cd−1) which does not fix x, and we have σ({yd−1, y0}) =
{yd−1, y0}. Then the extension h of σ over the sphere maps the face A1 to a face incident
to both xd−1 and x1. However, such a face does not exist by the planarity, a contradiction.
Therefore, we may assume that there is no edge between yi+1 and xi+2 in addition
and hence we can define the 3-coloring ci for all i. Furthermore, there is an automorphism
σi ∈ Aut(G, ci) with σi(x) = xi; if σi(x) = x, then σi is the identity map. Let hi be the
extension of σi over the sphere. Then h0(A0) is a face incident to x0 and x2 and h1(A1)
is a face incident to x1 and x3. However, these faces block the existence of each other.
Therefore, there exists no vertex of degree at least 5 in G.
Now we may assume that G consists of only vertices of degree 3 and 4 since G is
3-connected. Furthermore, we have 2|E(G)| = 4|V (G)| − 8 by Euler’s formula for a
quadrangulation G on the sphere. This implies that G has exactly eight vertices of degree
3 in this case. To determine the structure of G, we shall show the following claim:
Claim 1. Let x1y1x2y2 and x2y2x3y3 be the boundary cycles of two faces A1 and A2
sharing an edge x2y2. Then deg y1 = deg y3 and deg x1 = deg x3.
First assume that deg y2 = 4 and let y′1, x
′
2 and y
′
3 be the three other vertices lying
around y3 so that x1y′1x
′
2y2 and y2x
′
2y
′
3x3 bound two faces incident to y2 other than A1
and A2. Under this assumption, we shall show that there is an automorphism σ ∈ Aut(G)
which exchanges y1 and y3, fixing the edge x2y2; this implies the claim.
Consider a 3-coloring c : V (G) → {1, 2, 3} with c(x1) = c(x2) = c(x3) = 3. Since
G is not 3-distinguishing colorable, there is a non-trivial automorphism σ ∈ Aut(G, c). If
σ(y2) = y2, then σ exchanges x1 and x3, fixing x2; otherwise, σ would be the identity
map. This implies that σ exchanges y1 and y3, fixing x2y2 and hence it is the desired one
in this case. Thus, we may assume that σ(y2) is another vertex different from y2, say z,
and is adjacent to all of x1, x2 and x3. If z coincides with neither y1 nor y3, then at least
one of x1zx2 and x2zx3 forms a corner of a face since deg z = 4, and either {x1, x2} or
{x2, x3} would become a 2-cut of G, which is contrary to G being 3-connected. Thus, we
may assume that z = y3, up to symmetry, and there is an edge x1y3.
Since x1 is adjacent to y1, y′1, y2 and y3 and has degree 4, x1 is not adjacent to y
′
3.
The edge x1y3 blocks the existence of an edge between x2 and y′3. Thus, we can define
another 3-coloring c′ : V (G) → {1, 2, 3} of G by c′(x1) = c′(x2) = c′(y′3) = 3 and
there is a non-trivial automorphism σ′ ∈ Aut(G, c′) with its extension h′ since G is not
3-distinguishing colorable. Clearly, we have h′(A1) = A1 since σ′({x1, x2}) = {x1, x2}.
If σ′ exchanges x1 and x2, then there must be an edge σ′(x1)σ′(y3) = x2y′1. However, its
pre-image x1y3 blocks the existence of such an edge by the planarity. This implies that σ′
fixes x1, y1, x2, y2 and y′3, which would force σ
′ to be the identity map, a contradiction.
Therefore, this is not the case and only the previous case happens as we want.
Now assume that deg y2 = 3 and let x1y2x3y4 be the boundary cycle of the third
face incident to y2. If deg x2 = 4, then we can follow our arguments in the last three
paragraphs, exchanging xi and yi, to show the existence of σ and hence deg y1 = deg y3
and deg x1 = deg x3. Thus, we may assume that deg x2 = 3 and let y1x2y3x4 be the
boundary cycle of the third face incident to x2.
Suppose that deg y1 6= deg y3. Without loss of generality, we may assume that deg y1
= 3 and deg y3 = 4. Applying the first case to the two faces sharing x2y3, we conclude that
174 Ars Math. Contemp. 4 (2011) 165–175
deg x3 = deg x4 and deg y1 = deg y2 = 3. Consider a 3-coloring c : V (G) → {1, 2, 3}
of G with c(y2) = c(y3) = 3. Since G is not 3-distinguishing colorable, there is a non-
trivial automorphism σ ∈ Aut(G, c). Since deg y2 6= deg y3 = 4, σ fixes y2 and y3,
and hence it exchanges x2 and x3; it would be the identity map otherwise. Thus, we have
deg x2 = deg x3 = deg x4 = 3 and deg y1 = deg y4 = 3.
If deg x1 = 3, then there must be an edge x4y4 so that x1y1x4y4 bounds a face and we
find that y3 would be a cut vertex of G, contrary to G being 3-connected. Thus, we have
deg x1 = 4. Let y5 be the fourth neighbor of x1 and let x5 be the fourth neighbor of y3. The
degree conditions we have concluded imply that G consists of a cycle y1x2y2x3y4x5y5x4
of length 8 and the vertices x1 and y3 of degree 4; x1 is adjacent to all yi’s but y3 while
y3 is adjacent to all xi’s but x1. Consider a 3-coloring c′ : V (G) → {1, 2, 3} of G with
c′(y1) = c
′(x3) = 3. Since the cycle of length 8 contains all vertices of degree 3 in G, any
automorphism σ′ ∈ Aut(G, c′) preserves the cycle and fixes y1 and x3. This implies that σ′
would be the identity map, contrary to G not being 3-distinguishing colorable. Therefore,
we have deg y1 = deg y3 and deg x1 = deg x3 similarly.
Now we have just proved Claim 1. By the claim, we can conclude that the degrees
appear around all faces in the same pattern. If there are adjacent vertices of degree 3, then
the claim forces all of their neighbors to have degree 3 and we find that G is isomorphic to
Q3, which is one of the exceptions in the theorem. Therefore, there are only two patterns
of degrees around a face, (i) (3, 4, 3, 4) and (ii) (3, 4, 4, 4); (4, 4, 4, 4) is excluded since G
has eight vertices of degree 3. However, it is clear that G is isomorphic to R(Q3) in Case
(i), which should be excluded as the second exception.
e e eu u u u
e e e
u
u ue






@
@
@
@
@
@
@
@
@
@
@
@










Z
Z
Z
Z
@
@
@
@




@
@


i
i i
y
y′
xx′ A
Figure 2: A local structure of G
On the other hand, we find that G is isomorphic to R(R(Q3)), with the local structure
depicted in Figure 2 in Case (ii), as follows. First look at a faceA with two white vertices y
and y′ and suppose that deg y = 4 and deg y′ = 3. The four faces incident to y form a big
square containing y inside. Its four corners are white vertices of degree 3 and its sides are
divided by black vertices of degree 4 by Claim 1. We can find such a square for each white
vertex of degree 4 and conclude that such six squares form a cube including the whole of
G. If we denote the cube by Q3, then G can be regarded as R(R(Q3)).
The local structure of G in Figure 2 consists of fourteen distinct vertices and the black
vertices have degree 4. Consider a 3-coloring c of G such that the two white vertices and
the one black vertex encircled get color 3. Take any automorphism σ ∈ Aut(G, c) with its
extension h. Since deg y 6= deg y′, σ fixes y, y′ and x. Furthermore, h cannot flip the face
G. Fijavž et al.: 3-Connected planar graphs are 5-distinguishing colorable. . . 175
A since x 6= x′. This implies that σ is the identity map. Therefore, c is a 3-distinguishing
coloring and hence G would be 3-distinguishing colorable, contrary to our assumption on
G. Thus, this is not the case and the theorem follows.
4 For further studies
Following our proof of Theorem 1.2, we can conclude that χD(G) ≤ χ(G) +α for a small
integer α = 1 or 2 in each case. More detailed arguments could give a kind of structural
characterization on the distinguishing chromatic numbers of 3-connected planar graphs.
The case of planar triangulations has been settled in [7] by Sano.
References
[1] M. O. Albertson and K. L. Collins, Symmetry breaking in graphs, Electronic J. Combin. 3
(1996), R18.
[2] B. Bogstad and L. J. Cowen, The distinguishing number of the hypercube, Discrete Math. 283
(2004), 29–35.
[3] K. L. Collins and A. Trenk, The distinguishing chromatic number, Electronic J. Combin. 13
(2006), R16.
[4] T. Fukuda, S. Negami and T. Tucker, 3-Connected planar graphs are 2-distinguishable with few
exceptions, Yokohama Math. J. 54 (2008), 143–153.
[5] S. Negami, Uniqueness and faithfulness of embedding of toroidal graphs, Discrete Math. 44
(1983), 161–180.
[6] S. Negami and S. Sakurai, Distinguishing chromatic numbers of planar graphs, Yokohama Math.
J. 55 (2010), 179–188.
[7] T. Sano, The distinguishing chromatic number of triangulations on the sphere, to appear in Yoko-
hama Math. J., 2011.
[8] H. Whitney, Congruent graphs and the connectivity of graphs, Amer. J. Math. 54 (1932), 150–
168.