Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 5 (2012) 175–188
On list-coloring extendable outerplanar graphs∗
Joan P. Hutchinson
Macalester College, St. Paul, MN 55105, USA
Received 7 November 2010, accepted 7 September 2011, published online 1 February 2012
Abstract
We investigate a variation on Thomassen’s 2- and 3-extendability of precoloring exten-
sions for list-coloring graphs. For an outerplanar graph G with i, j ≤ 2, we say that G is
{i, j}-extendable if for every pair of nonadjacent vertices x and y, whenever x is assigned
an i-list, y is assigned a j-list, and all other vertices have a 3-list, G is list-colorable. We
characterize the {1, 1}- and the {1, 2}-extendable outerplanar graphs and prove that every
outerplanar graph is {2, 2}-extendable.
Keywords: Graph list-coloring, coloring extendability, outerplanar graphs.
Math. Subj. Class.: 05C15
1 Introduction
In C. Thomassen’s celebrated theorem that every planar graph is 5-list-colorable [7] (see
also [1]), he proves a stronger result.
Theorem 1.1. If G is a plane near-triangulation with outer cycle C, if two consecutive
vertices of C are precolored (with different colors), if all other vertices of C have a 3-list,
and if every other vertex of G has a 5-list, then the precoloring extends to a list-coloring of
G.
In [8] he calls these conditions the property of being 2-extendable, and characterizes the
planar graphs that are 3-extendable. That is, if G is a plane near-triangulation with outer
cycle C, if three consecutive vertices of C, v1, v2, v3, are properly precolored, if every
other vertex on C has a 3-list, and if every other vertex of G has a 5-list, then the graph is
called 3-extendable with respect to the path v1, v2, v3 if it is list-colorable. Not all plane
graphs are 3-extendable with respect to every 3-path on the outer cycle.
We consider an analogous list-coloring problem when, in a plane graph with outer
facial walk W , two nonadjacent vertices are precolored, the remaining vertices of W have
∗In memory of Michael O. Albertson, 1946–2009.
E-mail address: hutchinson@macalester.edu (Joan P. Hutchinson)
Copyright c© 2012 DMFA Slovenije
176 Ars Math. Contemp. 5 (2012) 175–188
3-lists, and all other vertices have 5-lists. When the graph is list-colorable, we say it is
{1,1}-extendable. Not all plane graphs are {1, 1}-extendable. More generally we consider
the cases when two nonadjacent vertices have lists of size i and j, with i, j = 1 or 2,
and call these {i, j}-extendable when there is a list-coloring. In this paper we consider
outerplanar graphs with nonadjacent vertices x and y, with x having an i-list, y a j-list,
and all other vertices having a 3-list. We characterize the {1, 1}-extendable and {1, 2}-
extendable outerplanar graphs and prove that every outerplanar graph is {2, 2}-extendable.
We formulate questions about possible generalizations of these results to all planar graphs.
Albertson [2] has asked whether there is a distance d > 0 such that if vertices of a
set P , mutually at distance at least d in a planar G, are precolored, then the precoloring
extends to a 5-list-coloring of G; Tuza and Voigt [9] have shown that in general distance
4 is not enough. In [3] we prove that the answer is yes when P consists of vertices on a
common face and mutually at distance at least three. Thus these graphs are {1, 1}-”5-list-
extendable,” meaning that all vertices except for P must have 5-lists. In contrast suppose
G is a plane near-triangulation with outer cycle C containing two nonadjacent precolored
vertices, with all other vertices of C having a 4-list, and with all other vertices having a
5-list. Then in Section 6, using the techniques of [3], we show that with these sizes of lists
on vertices of C all planar graphs are {1, 1}-”4-list-extendable.”
2 Background
We follow the terminology of [6, 7, 10]. Let G be a graph. When G is planar and embedded
in the plane, we call it a plane graph. For every v ∈ V (G), let L(v) be a list of colors
assigned to v. When |L(v)| = 1, we may say that v is precolored with its one available
color. G is said to be L-list-colorable (or when L is clear, list-colorable) when the vertices
can be properly colored so that each vertex v receives a color from L(v). As in [7], it is
natural to consider near-triangulations for this coloring problem. A plane graph becomes a
(plane) near-triangulation by the addition of edges so that every interior, finite face becomes
bounded by three edges; such a face is called a triangle. The addition of these edges only
makes the coloring problem more difficult, yet we remain in the class of plane graphs.
An outerplanar graph is one that has a plane embedding in which all vertices lie on
the exterior, infinite face; when it is so embedded, it is called an outerplane graph. Ev-
ery outerplane graph can be extended to an edge-maximal, 2-connected, near-triangulation
that remains outerplane. Then all vertices lie on a cycle that bounds the exterior face,
and all interior faces are triangles. We shall also consider 1-connected, outerplane near-
triangulations in which all vertices lie on a walk that bounds the exterior face, and all inte-
rior faces are triangles. Associated with such a 1-connected, outerplane near-triangulation
is the block-cutpoint tree; see [10].
Here is an immediate consequence of Thm. 1.1.
Corollary 2.1. Let G be a 1-connected near-triangulation with outer boundary W , and
let x, y ∈ V (W ). If x and y are adjacent and have, respectively, an i-list and a j-list,
i, j = 1, 2, or 3, if all vertices of W \{x, y} have a 3-list, and all vertices of V (G)\V (W )
have a 5-list, then G is list-colorable unless x and y have the same 1-list.
Proof. The vertices x and y can always be properly (pre) list-colored under these hypothe-
ses. The result follows from Thm. 1.1 when G is 2-connected. If G has cut-vertices, then
since the block B containing x and y can be list-colored, that list-coloring extends to the
rest of G by Thm. 1.1.
J. P. Hutchinson: On list-coloring extendable outerplanar graphs 177
Because of Cor. 2.1 we consider list-coloring extensions of two nonadjacent vertices.
First we consider the problem for 2-connected, outerplane graphs and then expand the result
to outerplane graphs with cut-vertices and in which the nonadjacent vertices lie in different
blocks. We note that Cor. 2.1 applied to outerplane near-triangulations can be proved easily
and directly without reference to Thm. 1.1.
Definition 2.2. Let G be a 2-connected near-triangulation with outer cycle C and nonad-
jacent vertices x, y ∈ V (C). Let i, j ∈ {1, 2}.
1. G is said to be {i, j}-extendable with respect to (nonadjacent) vertices x, y, if when-
ever x is assigned an i-list L(x), y is assigned a j-list L(y), every vertex v ∈
V (C) \ {x, y} is assigned a 3-list L(v), and every vertex w ∈ V (G) \ V (C) is
assigned a 5-list L(w), then G is L-list-colorable.
2. G is said to be {i, j}-extendable if for every choice of nonadjacent x, y ∈ V (C), it
is {i, j}-extendable with respect to vertices x and y.
In [8] Thomassen characterizes the 3-extendable near-triangulations with respect to a
3-path of vertices on the outer cycle in terms of ”broken wheels” and ”generalized wheels.”
Needed for our study of outerplane graphs, a broken wheel is the near-triangulation that
consists of a k-cycle on v1, v2, . . . , vk plus all diagonals from v1: v1v3, v1v4, . . . , v1vk−1.
(This is a k-wheel minus the edge v2vk.)
Here is a corollary that follows immediately from the 3-extendability theorem and proof
of [8].
Corollary 2.3. Let G be a 2-connected, outerplane near-triangulation with outer cycle
C = x1, x2, ..., xn. Reading subscripts modulo n,
1. for i = 1, 2, ..., n, G is 3-extendable with respect to the 3-path xi, xi+1, xi+2 if and
only if xi is adjacent to xi+2, and
2. for i = 1, 2, ..., n, G is not {1, 1}-extendable with respect to xi, xi+2 (assuming that
these vertices are not adjacent).
Proof. (1.) If xi and xi+2 are adjacent, then a proper coloring of xi, xi+1, xi+2 extends to
G by Thm. 1.1.
(1. and 2.) If xi and xi+2 are not adjacent, when L(xi) = {a}, L(xi+2) = {c}
with a 6= c, and L(xi+1) = {a, b, c}, then there is exactly one list-coloring of the 3-path
xi, xi+1, xi+2, and by [8] this does not extend since G must contain a broken wheel at
xi, xi+1, xi+2.
Similarly one can check that for i = 1, 2, ..., n, G is not {1, 2}-extendable with respect
to xi, xi+2 (when xi and xi+2 are not adjacent) if and only if the degree of xi+1 is odd.
G is always {2, 2}-extendable with respect to xi, xi+2. These results will follow also from
those of Theorem 3.3.
3 {i, j}-extendability of 2-connected, outerplane near-triangulations,
i, j ≤ 2
For later work, we include all 2-connected, outerplane graphs in the beginning of this sec-
tion.
178 Ars Math. Contemp. 5 (2012) 175–188
Definition 3.1. Let x and y be nonadjacent vertices of a 2-connected, outerplane graph G.
Let T be the weak dual of G with each vertex of T representing an interior region of G.
Let px,y represent the shortest path in T from a region incident with x to a region incident
with y, and let the fundamental x − y subgraph of G, Gx,y , consist of the subgraph of G
on these same regions, their edges and vertices.
An example is shown in Figure 1(a) when G is a near-triangulation, and in 1(c) when
G is not a near-triangulation. The corresponding Gx,y are illustrated in (b) and (d). In the
former case Gx,y is also a 2-connected, outerplane near-triangulation in which x and y are
two, and the only two, vertices of degree 2; see Figure 1(b). In the latter case, edges can be
added to interior faces of Gx,y so that x and y are precisely the two vertices of degree 2;
see Figure 1(d).
x
y
x
y
x
y
x
y
Figure 1: (a) An outerplanar near-triangulation G with selected vertices x and y, (b) Gx,y ,
(c) a non-near-triangulation G′ with selected vertices, x and y, (d) G′x,y .
Proposition 3.2. Let x and y be nonadjacent vertices of a 2-connected, outerplane graph
G with fundamental x − y subgraph Gx,y . If |L(v)| ≤ 2 for v = x, y, and |L(v)| = 3 for
all v ∈ V (G) \ {x, y}, then G can be list-colored if and only if Gx,y can be.
Proof. If Gx,y can be list-colored, then this extends to a list-coloring of G by Thm. 1.1.
In the rest of this section we focus on 2-connected, outerplane near-triangulations in
which there are precisely two degree-2 vertices and these two are the vertices with small
lists; in a near-triangulation, these two cannot be adjacent. The essence of the situation is
illustrated in Figure 2.
Notice that 2-connected, outerplane near-triangulations are uniquely 3-colorable so that
we may talk about the 3-color class of x, CCx. Thus in Figure 2(a), x and y lie in the same
color class, CCx, and in Figure 2b, y /∈ CCx. Here is the goal of this section.
Theorem 3.3. Let G be a 2-connected, outerplane near-triangulation with exactly two
degree-2 vertices x and y.
1. G is not {1, 1}-extendable with respect to x and y.
2. G is not {1, 2}-extendable with respect to x and y if and only if y ∈ CCx.
3. G is {2, 2}-extendable with respect to x and y.
J. P. Hutchinson: On list-coloring extendable outerplanar graphs 179
x
8a<
y
8b,c<
8a,b,c<
8a,b,c<
x
8a<
y
8d<
8a,b,c< 8b,c,d<
8a,b,c< 8_,_,_<
Figure 2: (a) A non-{1, 2}-extendable graph, (b) a non-{1, 1}-extendable graph.
In addition we will characterize the lists that make each G non-extendable in (1) and
(2). Thm. 3.3 has also been proved in a different manner by Axenovich and Lastrina [4] as
they explore additional conditions that ensure that a graph is {2,2}-extendable with respect
to two vertices.
Let G be a 2-connected, outerplane near-triangulation with exactly two degree-2 ver-
tices x and y. We label the vertices of G as follows: let x = v0 and label its neighbors v1
and v2. Without loss of generality v1 has degree 3 in G; label its third neighbor v3. Then
the triangle {v1, v2, v3} lies on one side of the edge v2v3, and the third (unlabeled) vertex
of the triangle lying on the other side of v2v3 is labeled v4. We continue labeling vertices
by the succession of triangles, each incident with the preceding. In the final triangle con-
taining y, the neighbors of y will have been labeled vj and vn−2 for some j < n − 2, and
y is labeled y = vn−1. For i = 2, 3, . . . , n − 1, let Gi denote the induced subgraph of G
on vertices v0, v1, . . . , vi. For i = 2, ..., n − 1, each triangle consists of {vti , vi−1, vi} for
some ti < i− 1, and we call vi−1 and vti the predecessors of vi. An example is shown in
Figure 3(a).
x y
v1 v5 v9 v11 v12
v3 v6
v10
v2 v4 v7 v8 v13
x y8b3,d3<
8a2,b2,d2<8_,_,_<8a3,b3,d3<
8a3,b2,d2<
8a2,b2,d2< 8a3,b3,d3<
8a<
8a,b,c< 8a1,b1,d1<
8a1,b,c< 8a2,b1,d1<
8a,b,c< 8a1,b1,d1<8_,_,_<
Figure 3: (a) A labeled, 2-connected, outerplane near-triangulation, (b) the graph with a set
of noncoloring lists.
180 Ars Math. Contemp. 5 (2012) 175–188
We note some additional properties of the near-triangulation G: Every triangle of G
contains precisely one vertex of CCx, the color class of x in a 3-coloring. With a precol-
oring of x, the remaining graph is 3-list-colorable by Thm. 1.1, though maybe not when y
has a small list. The sequential list-coloring algorithm of G \ {y} begins by extending the
coloring of x to its two neighbors and then in general extends to the next-indexed vertex,
adjacent to two colored neighbors. With 3-lists there is always a color available for each
extension in G \ {y}.
We enumerate and count the number of possible list-colorings of vertex vi in Gi, using
variables C(i) and m(i) = |C(i)|; we may say that C(i) is the C-set and m(i) the m-value
of vi. Suppose |L(x)| = 1 and |L(v)| = 3 for v ∈ V (G) \ {x, y}. For i = 0, 1, . . . , n− 2
let C(i) ⊆ L(vi) be defined by: C(0) = L(v0) and C(1) = L(v1) \ C(0). For i ≥ 2,
vi lies on a triangle formed with its two predecessors vi−1 and vti for some ti < i − 1.
We define C(i) ⊆ L(vi) to be the list of colors that are possible on vi, given the lists of
possible colors C(i − 1) and C(ti). In other words C(i) ⊆ L(vi) contains the color a
if and only if there is a list-coloring of Gi in which vi receives color a. As we’ve noted,
m(i) ≥ 1 for all i ≤ n− 2.
For example when |L(x)| = 1, for i = 1, 2 C(i) = L(vi) \C(0) so that m(i) = 2 or 3.
As seen in Figure 2 with C(0) = {a}, m(1) = 2 when L(v1) = {a, b, c}, and m(2) = 2
when L(v2) = {a, b′, c′}. In these cases C(0) is disjoint from C(1) and from C(2) with
v1, v2 /∈ CCx. Continuing with this example, m(3) = 1 if and only if L(v1) = L(v2) =
{a, b, c} and L(v3) = {b, c, d} where d may or may not equal a, but not b or c. In this case
C(1) = C(2), m(1) = m(2) = 2, C(3) = {d}, |C(1) ∩ L(v3)| = 2, and C(3) is disjoint
from C(1) and C(2). Similarly m(3) = 2 if and only if L(v1) = L(v2) = {a, b, c} and
L(v3) = {b, d, e} or {c, d, e} where d or e may equal a. In this case again C(1) = C(2),
m(1) = m(2) = 2, |C(1) ∩ L(v3)| = 1, and C(3) = {d, e} is disjoint from C(1) and
C(2). One can easily check that when C(1) 6= C(2) or when m(1) or m(2) = 3, then
C(3) = L(v3) and m(3) = 3.
In most cases m(i) = 3, but lists that prevent list-coloring are constrained ones on the
vertices of CCx and their predecessors. Specifically we will characterized when for every
vi ∈ CCx, m(i) = 1, and this characterization will lead to lists that prevent list-coloring.
Lemma 3.4. Let G be a 2-connected, outerplane near-triangulation with exactly two
degree-2 vertices, with notation as above, and with all vertices having 3-lists except that
|L(x)| = 1 and |L(y)| ≤ 2. For i > 0,
1. when vi ∈ CCx, m(i) < 3 if and only if vi’s predecessors have C(i − 1) = C(ti),
m(i− 1) = 2, and C(i− 1) ∩ L(vi) 6= ∅,
2. when vi ∈ CCx and m(i) < 3 and vj is a predecessor of vi, then C(j) and C(i) are
disjoint,
3. when vi /∈ CCx, m(i) ≥ 2, and
4. if vivj is an edge with j < i, C(i) = C(j), and m(i) = 2, then vi and vj are
adjacent to vk in CCx, k < i, with m(k) = 1.
Proof. The proof is by induction on i, and the base cases were presented in a preceding
paragraph. Let i > 3 and vi ∈ CCx. If the conditions of 1 hold, then m(i) < 3. If
m(i) < 3, by induction vti and vi−1 satisfy condition 3. Since m(ti),m(i − 1) ≥ 2 and
m(i) < 3, then we must have m(ti) = m(i− 1) = 2 with C(ti) = C(i− 1) implying that
m(i) = 1 or 2 depending on whether |C(i− 1)∩L(vi)| = 2 or 1, respectively. In addition
J. P. Hutchinson: On list-coloring extendable outerplanar graphs 181
let j = i − 1 or ti so that vj is a predecessor of vi. Then since C(i − 1) ∩ L(vi) 6= ∅,
C(i− 1) = C(ti) is disjoint from C(i) and condition 2 holds.
Let vivj , j < i, be an edge with C(i) = C(j) and m(i) = 2 so that vj is a predecessor
of vi. If the other predecessor of vi is vj′ with j′ < i, then if m(j′) = 3, also m(i) = 3,
a contradiction. If m(j′) = 1, then vj′ ∈ CCx by induction and condition 3 so that
condition 4 holds. Otherwise m(j′) = 2. Note that if C(j) 6= C(j′), then m(i) = 3. Thus
C(j′) = C(j) = C(i), but that is impossible, and we conclude that condition 4 holds.
If vi /∈ CCx, then one predecessor of vi, say vj , lies in CCx and the other, vj′ , is not
in CCx. By induction m(j′) ≥ 2, and if m(j) = 3, then m(i) = 3, and if m(j′) = 3,
then m(i) ≥ 2 as claimed. Thus assume m(j′) = 2 and m(j) ≤ 2. If j′ < j, then vj′ is
a predecessor of vj and by condition 2, C(j) and C(j′) are disjoint implying m(i) ≥ 2. If
j < j′ and m(j) = 1, then necessarily C(j) and C(j′) are disjoint, implying m(i) ≥ 2.
If j < j′ and m(j) = 2, then by induction and condition 4, C(j) 6= C(j′), implying that
m(i) ≥ 2. In all cases condition 3 holds.
Corollary 3.5. Let G satisfy the hypotheses of Lemma 3.4.
1. If vivj is an edge with m(i) = 1 and m(j) = 2, then C(i) and C(j) are disjoint.
2. If vivj is an edge with j < i, C(i) = C(j), and m(i) = 2, then vi, vj /∈ CCx.
3. If vivj is an edge, vi ∈ CCx, C(i) 6= C(j) but m(i) = m(j) = 2, then C(i) and
C(j) are disjoint.
Proof. 1. If i < j, then this is immediate. If j < i, then vj is a predecessor of vi, and
by Lemma 3.4(2) the sets are disjoint.
2. This follows from Lemma 3.4(4).
3. If j < i, this follows from Lemma 3.4(2). If i < j, let vi′ be the other predecessor
of vj . By Lemma 3.4(3), m(i′) ≥ 2. If m(i′) = 3, then m(j) = 3, a contradiction.
Thus m(i′) = 2. If C(i) 6= C(i′), then m(j) = 3, a contradiction. Thus C(i) =
C(i′) and since m(j) = 2, C(i) and C(j) must be disjoint.
Proposition 3.6. Let G be a 2-connected, outerplane near-triangulation with exactly two
degree-2 vertices and with notation as above. Suppose |L(x)| = 1 and |L(y)| ≤ 2. Then
G is not list-colorable if and only if for each vi ∈ CCx, m(i) = 1 and
1. if y = vn−1 ∈ CCx, then its predecessors have C(n−2) = C(tn−1), m(n−2) = 2,
and L(y) ⊆ C(n− 2), or
2. if y /∈ CCx, then |L(y)| = 1 and for its predecessor vi ∈ CCx, C(i) = L(y).
Proof. If m(i) = 1 for every vi ∈ CCx and conditions (1) or (2) hold, then G is not
list-colorable.
Conversely suppose G is not list-colorable; we know that G \ {y} is list-colorable. If
y ∈ CCx, then its two predecessors do not lie in CCx and by Lemma 3.4(3) have m-values
at least 2. Since G is not list-colorable, they must have equal C-sets of size 2 with L(y)
a subset of these sets. If y /∈ CCx, then one predecessor, say vi, lies in CCx, the other,
vj , does not and m(j) ≥ 2. If m(i) = 3, then G would be list-colorable implying that
m(i) < 3. If m(j) = 3, then G is not list-colorable only when the conditions of 2 hold.
Similarly if m(i) = 1 and m(j) = 2, then by Cor.3.5(1) C(i) and C(j) are disjoint and the
182 Ars Math. Contemp. 5 (2012) 175–188
conditions of 2 hold. Thus suppose m(i) = 2 and m(j) = 2. By Cor.3.5(2), C(i) 6= C(j)
and by Cor.3.5(3) C(i) and C(j) are disjoint. Thus G is list-colorable, a contradiction. We
conclude that conditions 1 or 2 must hold.
In summary, for every 2-connected, outerplane near-triangulation with exactly two
degree-2 vertices, there is a set of 3-lists such that when the degree-2 vertices are pre-
colored (or one has a choice of two colors), the graph is not list-colorable. We call such
lists noncoloring lists.
As the examples of Figures 2(b) and 3(b) show, there may be some lists within such a
non-list-colorable graph that are not constrained, but lists are constrained on an important
subgraph of G, a chain of diamonds, which we shall use again in Section 4. We relabel
the vertices of this chain by letting x0 = x, x3, x6, ..., x3k be the vertices of CCx listed
with increasing index, and suppose that each has m-value 1. Then by Lemma 3.4(1), for
i = 1, . . . , k each x3i has two predecessors, x3i−1 and x3i−2, with identical C-sets and m-
value 2, and by 3.4(4) these two have a naturally associated x3i−3 ∈ CCx. The subgraph
on these vertices and y forms the chain of diamonds and appears as in Figure 4 where we
illustrate the cases when y ∈ CCx so that y = x3k, and when y /∈ CCx.
x y=x3 k
x1 x4
... ...
x3 i-2
x3 x6
x3 i-3 x3 i
x2 x5 x3 i-1
x3 k-3
x3 k-2
x3 k-1
x y=x3 k+1
x3 k
x1 x4
... ...x3 x6
x3 i-3 x3 i
x2 x5
x3 i-2
x3 i-1
x3 k-3
x3 k-2
x3 k-1
Figure 4: (a) Vertex y in CCx, (b) Vertex y not in CCx.
Corollary 3.7. Let G be a 2-connected, outerplane near-triangulation with exactly two
degree-2 vertices and with notation as above. If |L(x)|, |L(y)| ≤ 3 and all other vertices
have 3-lists, then there is a set of noncoloring lists if and only if
1. |L(x)| = |L(y)| = 1, and the lists satisfy the conditions of Prop. 3.6 (1) or (2), or
2. |L(x)| = 1, |L(y)| = 2 (or vice-versa), and the lists satisfy the conditions of
Prop. 3.6 (1).
Proof. If conditions (1) or (2) hold, then there is a set of noncoloring lists.
Conversely assume there is a set of noncoloring lists. We have noted that if either L(x)
or L(y) contains three colors, then the sequential list-coloring algorithm, beginning with y
or x, respectively, always extends to the whole graph. If |L(x)| = 1 and |L(y)| ≤ 2, then
by Prop. 3.6 the statement follows.
Suppose |L(x)| = |L(y)| = 2 with L(x) = {a, b}, and furthermore suppose that
beginning by coloring x with color a does not lead to a list-coloring of G. By Prop. 3.6,
J. P. Hutchinson: On list-coloring extendable outerplanar graphs 183
then y ∈ CCx and the lists are noncoloring. Then Lemma 3.4 and Prop. 3.6 tell us that the
graph contains a chain of diamonds, as in Figure 4, and also tell us explicitly about the lists
on this subgraph. Here are the noncoloring lists on the chain of diamonds subgraph, given
by Lemma 3.4 and Prop. 3.6 with labels as in Figure 4. Each list for xi, i > 0, is a triple
of distinct colors, but otherwise the colors may repeat. As in Figure 3(b), L(x0) = {a},
L(x1) = {a, b, c} = L(x2), L(x3) = {a1, b, c}, L(x4) = {a1, b1, d1} = L(x5), L(x6) =
{a2, b1, d1}, and in general for i = 2, ...k − 1 L(x3i) = {ai, bi−1, di−1}, L(x3i+1) =
{ai, bi, di} = L(x3i+2). Since these are noncoloring lists, L(y) = {bk−1, dk−1}.
Next we assume that initially coloring x with color b also leads to a non-list-colorable
graph; the conditions of Lemma 3.4 and Prop. 3.6 hold and constrain the lists on the chain
of diamonds. With x colored with b, then b does lie in both L(x1) and L(x2), and so
that there is only one possible color for L(x3), we must have a1 = a so that L(x3) =
{a, b, c}. Continuing we must have b1 = b and L(x4) = {a, b, d1} = L(x5), and we
must have a2 = a so that L(x6) = {a, b, d1}. Thus for i = 1, ..., k − 2, ai = ai−1 = a
and bi = bi−1 = b. In the final two triangles (before and including y) L(x3k−3) =
{ak−1, bk−2, dk−2} = {a, b, dk−2}, L(x3k−2) = {a, b, dk−1} = L(x3k−1). But now the
two possible colors on x3k−2 and x3k−1 are {a, dk−1} so that b = bk−1 can be used on y;
note that {ak−1, bk−1, dk−1} = {a, b, dk−1} are the triple of colors given to L(x3k−2) and
so are distinct.
Theorem 3.3 follows from Cor. 3.7.
4 {i, j}-extendability of 2-connected outerplane graphs, i, j ≤ 2
There are some outerplane graphs that are not near-triangulations whose list-colorability
follows immediately from the work of Section 3. Let G be a graph that consists of a
chain of diamonds joining vertices x and x3k with labels as in Figure 4. Suppose that for
i = 1, . . . , k−1, there is a path joining x3i−1 and x3i+2 or joining x3i−2 and x3i+1 with x3i
adjacent to some of the vertices of this path. In addition there may be a vertex y adjacent to
x3k and also joined by a path to one neighbor of x3k; x3k may be adjacent to some vertices
of this path, besides its endpoints. Call such a graph a supplemented chain of diamonds;
see Figure 5 for an example when y = x3k. The list-colorability of this graph depends
on and only on the list-colorability of its chain of diamonds subgraph. Thus the relevant
question is whether there is a 2-connected outerplane graph that is not a near-triangulation,
contains no chain of diamonds from x to y, and whose list-coloring does not extend; the
answer is no. See Figure 1(d) for an example that does not contain a chain of diamonds and
Figure reffig:5 for one that does contain a chain of diamonds. It is easy to check that the
former graph is {1, 1}-extendable and that there are lists making the latter not list-colorable
by continuing the lists as shown.
On the whole, except as described above, when G is not a near-triangulation, it is easier
to list-color. Notice that if G consists of a single cycle with two nonadjacent, precolored
vertices, then the precoloring always extends when there are 3-lists on all other vertices.
Thus we assume that G has at least two interior, finite faces. As before when |L(v)| ≤ 2
for v = x, y, and |L(v)| = 3 for all v ∈ V (G) \ {x, y}, by Prop. 3.2 we may assume
that G = Gx,y so that x and y have degree 2 and lie on different faces of G. There may
be additional vertices of degree 2, but now it must be the case that G can be extended
(by adding edges) to a 2-connected, outerplane near-triangulation in which x and y are
the two and only two vertices of degree 2. This is possible if and only if every interior
184 Ars Math. Contemp. 5 (2012) 175–188
x!a" y
v1
!a,b,c"
v5
!a1,b1,d1"
v9 v11 v12 v13
v3
!a1,b,c"
v6
!a2,b1,d1"
v10
v2!a,b,c" v4!a1,b1,d1" v7!_,_,_" v8 v14
Figure 5: A labeled non-near-triangulation that contains a chain of diamonds.
edge of G(= Gx,y) separates x and y; i.e., the removal of each interior edge and its two
end-vertices leaves x and y in different components; see Figure 1(c), (d).
Now we label vertices similarly; see Figure 5 for an example. Let x = v0 lie on a region
R with j + 1 vertices; the region has exactly one interior edge eR that lies on an additional
region R′. We label the other vertices of R with v1, . . . , vj in any manner provided that
when a vertex is labeled, it has a labeled neighbor of lower index and provided that vj lies
on eR. Then we label that region Rj and assume that the two end-vertices of eR = eRj
are vj and vj1 , j1 < j. In the region R
′ that is incident with Rj along edge eRj , we begin
the labeling from vj , using the same procedure as for Rj , until we reach the edge eR′ , if
it exists, and we conclude the labeling with largest indexed vertex, say vj′ , lying on eR′ .
This second region becomes Rj′ with edge eRj′ having endpoints vj′ and vj′1 , j
′
1 < j
′.
The only variation is that in the final region we choose to label y with vn−1 and then the
final region Rn−1. As before the sequential list-coloring algorithm list-colors G \ {y} by
coloring vertices in order of index, always possible since every vertex of G \ {x, y} has a
3-list. Note that regardless of the labeling, diagonals can be added to each interior region
that is not a triangle so that in the end the graph becomes Gt, which is a near-triangulation
with x and y being the vertices of degree 2.
Following the sequential list-coloring algorithm on G\{y}, we define C(i) and m(i) =
|C(i)|, i = 0, . . . , n − 2, as before. Since G is a subgraph of Gt, it follows that Ct(i) ⊆
C(i) and mt(i) ≤ m(i) for i = 0, . . . , n−2, where Ct(i) and mt(i) are the corresponding
C-sets and m-values of the near-triangulation Gt. Then by the results of Section 3, we
have the following.
Lemma 4.1. Let G be a 2-connected outerplane graph, let x, y ∈ V (G) be nonadjacent,
lying on two different interior faces, and such that every interior edge of G separates x and
y. If |L(v)| ≤ 2 for v = x, y, |L(v)| = 3 for v ∈ V (G) \ {x, y}, and with labeling as
above, then
1. if vertex vi has exactly one predecessor vj , then m(i) ≥ 2 and m(i) = 2 if and only
if m(j) = 1,
2. if vertex vi has two nonadjacent predecessors vj , vj′ , then m(i) ≥ 2 and m(i) = 2
if and only if m(j) = 1 or m(j′) = 1,
3. there is no edge of G joining two vertices with m-value 1,
4. if R is an interior region of G, then at most one vertex of V (R) has m-value 1,
J. P. Hutchinson: On list-coloring extendable outerplanar graphs 185
5. if m(i) < 3, then vi lies on a triangle with vertices vi1 , vi2 , i1, i2 < i, C(i1) = C(i2)
with m(i1) = 2, and C(i1) ∩ L(vi) 6= ∅,
6. if there is an edge vjvi, j < i, with equal C-sets of size 2, then there is a vertex vk,
k < i, that forms a triangle with vj and vi, and m(k) = 1,
7. if there is an edge of G joining two vertices with m-values 1 and 2, then their C-sets
are disjoint, and
8. if there is an edge vjvi, j < i, with C(i) 6= C(j) and m(i) = m(j) = 2, then C(i)
and C(j) are disjoint.
Proof. Many of these statements are immediate.
Statement (3) follows since mt(i) ≤ m(i) and in a near-triangulation there can be no
adjacent vertices with m-values 1.
For statement (4) suppose Rj is a region, j ≤ n− 1, with its least indexed vertex being
vi1 , 0 < i1 < j, lying also on Ri and the interior edge vivi1 between Ri and Rj for some
i < j. If m(i),m(i1) ≥ 2, then Rj contains no vertex with m-value 1. By (3) without
loss of generality we may assume m(i) = 1 and m(i1) ≥ 2. Then all other vertices have
m-value at least 2. The same argument holds when Rj is the region with least index and
contains vertex v0.
(5) If m(i) = 1 and vi has two predecessors, then by (2) they are adjacent, forming a
triangle. As we’ve seen in Lemma 3.4, this implies that the conditions of (5) are met. If
m(i) = 2, then by (2), (3) vi has two predecessors that form a triangle, implying that the
conditions of (5) are met.
(6), (7), (8) The proof is the same as for Lemma 3.4(4) and Cor 3.5(1), (3).
Proposition 4.2. Let G be a 2-connected outerplane graph, let x, y ∈ V (G) be nonadja-
cent, lying on two different faces, and such that every interior edge of G separates x and y.
If |L(v)| ≤ 2 for v = x, y, and |L(v)| = 3 for v ∈ V (G) \ {x, y}, with labeling as above,
then G is not list-colorable if and only if
1. G contains a chain of diamonds joining x and y, labeled as in Figure 4, m(3i) = 1
for i = 1, . . . , k− 1, and if y = x3k, then C(3k− 1) = C(3k− 2), m(3k− 1) = 2,
and L(y) ⊆ C(3k − 1), or
2. G contains a chain of diamonds joining x and v3k, labeled as in Figure 4(b), with y
adjacent to x3k, m(3i) = 1 for i = 1, . . . . , k, and |L(y)| = 1 with C(3k) = L(y).
The proof is immediate from Lemma 4.1 and the proof techniques of Prop. 3.6 and
Cor. 3.7.
Theorem 4.3. Let G be a 2-connected outerplane graph, let x, y ∈ V (G) be nonadjacent,
lying on two different faces, and such that every interior edge of G separates x and y.
1. G is not {1, 1}-extendable with respect to x and y if and only if G contains a chain
of diamonds joining x with y or x with a neighbor of y, and the conditions on lists
of Prop. 4.2 are satisfied.
2. G is not {1, 2}-extendable with respect to x and y if and only if G contains a chain
of diamonds joining x with y and the conditions on lists of Prop. 4.2(1) are satisfied.
3. G is {2, 2}-extendable with respect to x and y.
186 Ars Math. Contemp. 5 (2012) 175–188
Corollary 4.4. Let G be a 2-connected, outerplane graph that is not a near-triangulation,
let x, y ∈ V (G) be nonadjacent, lying on two different faces, and such that every interior
edge of G separates x and y. Then G is {i, j}-extendable for all i, j ≤ 2, unless G contains
a supplemented chain of diamonds with i = 1 and j ≤ 2.
5 {i, j}-extendability of outerplane graphs with cut-vertices
Just as Theorems 3.3 and 4.3 show the similarity of results for 2-connected, outerplane
near-triangulations and non-near-triangulations, so are the related results for 1-connected
outerplane graphs analogous. We present the details for the near-triangulation case.
Definition 5.1. Let x and y be nonadjacent vertices of an outerplane near-triangulation
G that is connected, but contains cut-vertices. Let Tbc be its block-cutpoint tree with x
lying in block Bi, y lying in Bj , and px,y the shortest path in Tbc from Bi to Bj so that
px,y = Bi, vi, . . . , Bj−1, vj−1, Bj with vi, vj−1 being cut-vertices on this shortest path.
Then the fundamental x − y subgraph Gx,y consists of the triangles, their vertices and
edges that comprise a shortest path of triangles in Bi from x to vi, then for each block Bk,
i+ 1 ≤ k ≤ j − 1, a shortest path of triangles from vk−1 to vk, and ending with a shortest
path of triangles in Bj from vj−1 to y.
Proposition 5.2. Let x and y be nonadjacent vertices of a connected, outerplane near-
triangulation G with cut-vertices and with fundamental x−y subgraph Gx,y . If |L(v)| ≤ 2
for v = x, y, and |L(v)| = 3 for v ∈ V (G) \ {x, y}, then G can be list-colored if and
only if Gx,y can be.
As in Prop. 3.2, the proof is an application of Thm. 1.1.
Now suppose that the outerplane near-triangulation G and its nonadjacent, degree-2
vertices x, y (with G = Gx,y) consist of x = v0 in block B1 with cut-vertex v1, which is
also in block B2, block B2 with cut-vertex v2, which is also in block B3, . . . , cut-vertex vk,
which is also in block Bk+1, and block Bk+1 that contains y = vk+1. Suppose |L(x)| = 1
and for all v ∈ V (G) \ {x, y}, |L(v)| = 3. Then by Prop. 3.6 if v1 ∈ CCx, there are
lists for V (B1) in which there are two forbidden colors on v1 (meaning they prevent list-
coloring) and so effectively in blocks B1 and B2 v1 has a reduced 1-list of possible colors.
If v1 /∈ CCx, then there are lists for V (B1) in which there is one forbidden color on
v1 so that in blocks B1 and B2 v1 has a reduced 2-list of possible colors. Thus in each
block Bi, which shares the cut-vertex vi−1 with Bi−1, though vi−1 begins with a 3-list
L(vi−1), L(vi−1) might be reduced to a 1- or 2-list because of non-list-colorings on Bi−1.
If L(vi−1) is reduced to a 2-list and vi /∈ CCvi−1 , then by Prop. 3.6, block Bi is always
list-colorable and L(vi) remains a 3-list. If L(vi) remains a 3-list for some i > 0, then the
remaining graph and the entire graph is list-colorable when |L(y)| ≥ 1 by Thm. 1.1. We
deduce the following; call x, y, and the cut-vertices of G the special vertices of G so that
each block contains two special vertices.
Theorem 5.3. Let x and y be nonadjacent vertices of a connected outerplanar near-
triangulation G = Gx,y with cut-vertices, labeled as above. If |L(v)| ≤ 2 for v = x, y and
|L(v)| = 3 for all v ∈ V (G) \ {x, y}, then G cannot be list-colored if and only if for at
most one block Bi with special vertices vi−1 and vi, vi /∈ CCvi−1 . More precisely,
1. G is not {1, 1}-extendable with respect to x and y if and only if for exactly one block
Bi with special vertices vi−1 and vi, vi /∈ CCvi−1 .
J. P. Hutchinson: On list-coloring extendable outerplanar graphs 187
2. G is not {1, 2}-extendable with respect to x and y if and only if for every block Bi
with special vertices vi−1 and vi, vi ∈ CCvi−1 .
3. G is always {2, 2}-extendable with respect to x and y.
Proof. Suppose G is not list-colorable, |L(x)| = 1, and there is a block Bi for which
vi /∈ CCvi−1 ; let i be the first index for which the latter holds. Then the reduced list-size
for vi−1 is 1 since two colors were forbidden on vi−1 in Bi−1. Then by Prop. 3.6 since
vi /∈ CCvi−1 , there is at most one forbidden color for vi, and L(vi) is reduced to two colors
for Bi and Bi+1. Then in Bi+1 and in every subsequent block we must have vi+1 in CCvi
and |L(y)| = 1 to prevent list-coloring. If there is no such block Bi, then condition (2)
holds.
If G is not list-colorable and |L(x)| = |L(y)| = 2, then at v1 there is at most one
forbidden color so that L(v1) has a reduced list of size 2. Then it follows that for each cut
vertex vi the reduced list is of size at least 2, and the final block has both special vertices
having lists of size at least 2. By Thm. 3.3 G would be list-colorable.
We note that Lemma 5 of [8] gives an instance of Thm. 5.3(3) on the limited class
of outerplanar graphs called ”generalized (broken) wheel strings,” though there a slightly
stronger conclusion is reached.
A theorem analogous to Thm. 5.3 holds for outerplane graphs that are not near-trian-
gulations, just as the conclusions of Thm. 3.3 hold for the conditions of Thm. 4.3, with the
presence of a chain of diamonds playing the role of CCx.
6 Some general results and questions
These results on outerplane graphs lend evidence for an affirmative answer to the following
question about arbitrary planar graphs:
Conjecture 6.1. Is every planar graph {2, 2}-extendable?
Let G[V ′] denote the induced subgraph on V ′ ⊆ V (G).
Corollary 6.2. Let G be a plane near-triangulation with outer cycle C. Let x and y
be nonadjacent vertices of C, and suppose |L(v)| ≤ 2 for v = x, y, |L(v)| ≥ 3 for
v ∈ V (C) \ {x, y}, and |L(v)| ≥ 5 for v ∈ V (G) \ V (C).
1. When G[C] is a near-triangulation, G is L-list-colorable if and only if G[C] is.
2. When all interior faces of G[C] have at most six-edges, G is L-list-colorable if and
only if G[C] is except possibly when the interior of some face contains a vertex
adjacent to at least five vertices on the face boundary, or contains an edge or a
triangle whose vertices are adjacent to six vertices on the face boundary.
3. G is L-list-colorable when |L(v)| ≥ 4 for v ∈ V (C) \ {x, y}.
4. When |L(v)| = 2 for v = x and y, G is L-list-colorable when in one subpath of C
joining x and y, there is at most one vertex with a 3-list and all others on this subpath
have 4-lists.
5. When |L(v)| = 2 for v = x and y, G is L-list-colorable when x = v1, v2, y = v3
are three consecutive vertices of C.
188 Ars Math. Contemp. 5 (2012) 175–188
Part (1) follows from Thm. 1.1. Part (2) follows from [5, 8]. Parts (3) and (4) follow
from the results of [3], and Part (5) is a corollary of Part (4). More explicitly for Part (3),
suppose |L(v)| ≥ 4 for v ∈ V (C)\{x, y}. Color x with one of L(x), say color a. Delete x
and delete color a, when present, from L(v) for every neighbor v of x. Since the resulting
graph satisfies the hypotheses of Thm. 1.1, it can be list-colored and that coloring gives a
list-coloring of G with x colored a; see [3].
Some additional results on the general case of Conj. 19 have been obtained by Axen-
ovich and Lastrina [4].
References
[1] M. Aigner and G. M. Ziegler, Proofs from THE BOOK, Springer, Berlin, 1991.
[2] M. O. Albertson, You can’t paint yourself into a corner, J. Combinatorial Theory, Ser. B, 73
(1998), 189–194.
[3] M. Axenovich, J. P. Hutchinson and M. A. Lastrina, List precoloring extension in planar graphs,
Discrete Math. 311 (2011), 1046–1056.
[4] M. Axenovich and M. A. Lastrina, personal communication, 2010.
[5] T. Böhme, B. Mohar and M. Stiebitz, Dirac’s map-color theorem for choosability, J. Graph
Theory 32 (1999), 327–339.
[6] B. Mohar and C. Thomassen, Graphs on Surfaces, Chapter 7, Johns Hopkins University Press,
Baltimore, 2001.
[7] C. Thomassen, Every planar graph is 5-choosable, J. Combinatorial Theory, Ser. B 62 (1994),
180–181.
[8] C. Thomassen, Exponentially many 5-list-colorings of planar graphs, J. Combinatorial Theory,
Ser. B 97 (2007), 571–583.
[9] Zs. Tuza and M. Voigt, A note on planar 5-list colouring: non-extendability at distance 4,
Discrete Math. 251 (2002), 169–172.
[10] D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, Upper Saddle River, NJ,
2001.