Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 5–24
More results on r-inflated graphs:
Arboricity, thickness, chromatic number and
fractional chromatic number
Michael O. Albertson ∗
Department of Mathematics and Statistics, Smith College, Northampton MA 01063 USA
Debra L. Boutin
Department of Mathematics, Hamilton College, Clinton, NY 13323 USA
Ellen Gethner
Department of Computer Science, University of Colorado Denver, Denver, CO 80217 USA
Received 3 July 2010, accepted 26 August 2010, published online 18 October 2010
Abstract
The r-inflation of a graph G is the lexicographic product G with Kr. A graph is said
to have thickness t if its edges can be partitioned into t sets, each of which induces a
planar graph, and t is smallest possible. In the setting of the r-inflation of planar graphs,
we investigate the generalization of Ringel’s famous Earth-Moon problem: What is the
largest chromatic number of any thickness-t graph? In particular, we study classes of
planar graphs for which we can determine both the thickness and chromatic number of
their 2-inflations, and provide bounds on these parameters for their r-inflations. Moreover,
in the same setting, we investigate arboricity and fractional chromatic number as well. We
end with a list of open questions.
Keywords: r-inflation, thickness, chromatic number, fractional chromatic number, arboricity.
Math. Subj. Class.: 05C15, 05C42, 05C10
1 Introduction
In 1890, P. J. Heawood published his famous article Map-colour theorem in the Quarterly
Journal of Mathematics [25] that illustrated the flaw in A.B. Kempe’s “proof” of the Four
Colour Theorem [33]. Heawood’s main intention was to investigate generalizations of the
∗Written posthumously.
E-mail addresses: dboutin@hamilton.edu (Debra L. Boutin), ellen.gethner@ucdenver.edu (Ellen Gethner)
Copyright c© 2011 DMFA Slovenije
6 Ars Math. Contemp. 4 (2011) 5–24
Four Colour Problem “of which strangely the rigorous proof is much easier [44].” The
Empire Problem (or M -pire problem, so coined by H. Taylor [21]), was such a problem:
one starts with a mapG and allows a country to consist of at mostM empires. Using Euler’s
formula, Heawood showed that the largest chromatic number of any M -pire map is at most
6M and was further able to prove that the bound was sharp for M = 2. In 1981 Herbert
Taylor proved that Heawood’s bound was sharp for M = 3 [21]. The M -pire problem was
settled completely by Jackson and Ringel in 1983 [29] with a general construction for an
M -pire map with chromatic number 6M for any M ≥ 2. Ringel’s interest in the M -pire
problem began long before that time: in 1959 he posed a minor variation in one special
case. Specifically, Ringel suggested in the case M = 2 that the countries should reside
on one sphere, while their respective colonies should reside on another, and then wondered
what the largest chromatic number of such a graph could be [38]. On the surface, this
change might have appeared to make the problem easier to solve. But such was not to be
case [28].
The largest chromatic number of a graph arising in Ringel’s variation has come to be
known [32] as the Earth-Moon problem, and such a graph as an Earth-Moon graph. The
Earth-Moon problem is famous, if not infamous, amongst graph colorers because the state-
of-the-art knowledge of the problem has remained remarkably static to this day. In 1959 the
largest chromatic number of any Earth-Moon graph was known to lie in {8, 9, 10, 11, 12};
the 8 is the smallest in the list of possibilities because Ringel achieved an Earth-Moon
decomposition of a map whose dual graph is K8. The 12 is the largest in the list of pos-
sibilities because an Earth-Moon map is a 2-pire map and hence Heawood’s upper bound
applies. In 1973, Thom Sulanke showed that the map whose dual graph is C5 ∨K6, a 9-
chromatic graph, was an Earth-Moon map [41]; his result became publicly known in 1980
when Martin Gardner published Sulanke’s decomposition of C5 ∨ K6 in the Scientific
American games column [20]. As of 1973 through the writing of this article, the largest
chromatic number of any Earth-Moon map is known to lie in {9, 10, 11, 12}.
Ringel’s Earth-Moon problem generalizes to many moons; to this end, a graph G is
said to have thickness t, written Θ(G) = t, if its edges can partitioned into t sets, each
of which induces a planar graph, and t is smallest possible. In that case Ringel’s Earth-
Moon problem can be rephrased as follows: What is the largest chromatic number of any
thickness-2 graph? More generally: What is the largest chromatic number of any thickness-
t graph? With the exception of t = 1, where the Four Color Theorem [7, 8, 6, 5, 39] applies,
and t = 2 as discussed above, the largest chromatic number of any thickness-t graph lies
in {6t− 2, 6t− 1, 6t} [31].
What makes finding the largest chromatic number of a thickness-t graph difficult?
Given an arbitrary graph G and a fixed positive integer t > 1, verifying that Θ(G) = t
is an NP-complete problem [35]. Similarly, given an arbitrary graph G and fixed positive
integer k > 2, verifying that χ(G) = k is also NP-complete [22, 23]. It appears, then, that
the strategy of starting with a graph of known thickness and finding its chromatic number,
or vice versa, will not often end in success. Thus it would be useful to have a collection of
graph families for which both the thickness and chromatic number are understood.
One of the first families of graphs with known thickness and chromatic number, apart
from (most) complete bipartite graphs [10, 9] and complete graphs [3, 43], is a subfamily
of Catlin’s graphs. Catlin’s graphs are the lexicographic product of cycle Cn with the
complete graph Kr. Thomassen describes these gaphs as the r-uniform replication of Cn
[42]. Plummer, Stiebitz, and Toft use the terminology r-inflation of Cn [37], which is
M. O. Albertson et al.: More results on r-inflated graphs. . . 7
what we use in this article. In [12] Catlin gave a formula for the chromatic number of
the r-inflation of Cn. In [11], Boutin, Gethner, and Sulanke showed that for n ≥ 4 the
3-inflation of Cn has thickness two.
In [24], the following challenge was offered: “Characterize those planar graphs G for
which the thickness of G[2] is precisely two,” where G[2] refers to the 2-inflation of G.
Much of the work in this paper and [2] was inspired by the challenge and some of its
generalizations; a large part of the appeal of the study of the chromatic number, thickness,
and other graph parameters of r-inflated graphs is that, in some instances, exact values can
be attained and upper bounds can be achieved. In [2] the current authors began the task of
finding the thickness of r-inflations and also included some results on chromatic number.
Two of the more significant reported results were the determination of the thickness of
the r-inflation of the icosahedral graph and the thickness of r-inflated trees. The latter
result can be used to obtain a bound on the thickness of G[r] using the arboricity of G. The
former achieved an upper bound for both thickness and chromatic number of edge maximal
r-inflated planar graphs.
In this article, we develop additional tools for investigating r-inflated graphs. These
tools are applied to determine exactly and give bounds for arboricity, thickness, chromatic
number, and fractional chromatic number of the r-inflation of the icosahedral graph, do-
decahedral graph, maximal planar graphs, trees, cycles, wheels, generalized series parallel
graphs, and planar undirected circulant graphs. In Sections 3, 4, and 5 we develop tools
and results about (respectively) arboricity, thickness, and fractional chromatic number of
r-inflated graphs. In Section 6 we use these tools to determine exact values or bounds for
these parameters in a variety of families of inflated planar graphs. A summary of results is
then displayed in a table in Section 7. We close with open questions in Section 8.
2 Basics
Definition 2.1. Let G be a graph; the r-inflation of G is the lexicographic product G[Kr],
and is denoted by G[r]. Call G[2] the clone of G.
Recall that the lexicographic product G[H] replaces every vertex of G with a copy of
H and places edges between all pairs of vertices in copies of H associated with adjacent
pairs of vertices of G. That is, the vertices of G[H] are V (G)×V (H) and there is an edge
between (g1, h1) and (g2, h2) if and only if g1 = g2 and h1 is adjacent to h2 in H (the
vertices are in the same copy of H) or g1 is adjacent to g2 in G (the vertices are in copies
of H associated with adjacent vertices in G).
By definition, we obtain G[r] by replacing each vertex of G by Kr and each edge of
G by K2r (which contains a Kr for each vertex of the edge). An r-inflation of G has the
following properties, all of which are straightforward to verify.
Observations:
1. If the number of vertices and edges of G are V and E respectively, the number of
vertices and edges of G[r] are rV and
(
r
2
)
V + r2E respectively.
2. G[sr] = (G[s]) [r]. In particular, for any complete graphKs and any positive integer
r, we have Ks[r] = Ksr.
3. Independence is invariant under inflation. That is, if the independence number of G
is α then the independence number of G[r] is α as well.
8 Ars Math. Contemp. 4 (2011) 5–24
4. If the clique number of G is ω, then the clique number of G[r] is rω.
5. If the chromatic number of G is χ then the chromatic number of G[r] is at most rχ.
6. Any edge of G (along with its incident vertices) induces a K2r in G[r].
7. If G is vertex transitive then so is G[r]. The same cannot be said of edge transitivity.
3 Arboricity and density
Throughout this paper we use the Nash-Williams formula [36] for arboricity of a graph.
That is, arb(G) = maxH⊆G
⌈
|E(H)|
|V (H)|−1
⌉
over all subgraphs H of G. Note that over a
given subset of vertices of G the maximum
⌈
|E(H)|
|V (H)|−1
⌉
occurs on the induced subgraph on
that subset. Thus it is sufficient to restrict our search to the induced subgraphs of G.
Definition 3.1. Given a graph G, call |E(G)||V (G)|−1 the density of G, denoted dens(G). The
graph is said to be uniformly dense if |E(G)||V (G)|−1 ≥
|E(H)|
|V (H)|−1 for all induced subgraphs H of
G.
Thus by Nash-Williams, if G is uniformly dense then arb(G) =
⌈
|E(G)|
|V (G)|−1
⌉
. Further-
more, using the fact that any planar graph on n vertices has at most 3n − 6 edges, it is an
easy consequence of Nash-Williams that any planar graph has arboricity at most three.
Note that the definition of density (and therefore uniform density) given here agrees
with the definition given in [13], but differs slightly from the one given in [27]. However,
these definitions agree on connected graphs. The following results from these papers are
useful in this work.
Theorem 3.2. [27] If G is a connected vertex transitive or edge transitive graph, then G is
uniformly dense.
Theorem 3.3. [13] If G is a tree, a maximal outerplanar graph, or a maximal planar graph,
then G is uniformly dense.
The following lemma and theorems are useful in finding the arboricity of r-inflated
trees and planar graphs.
Lemma 3.4. Let G be a graph, v ∈ V (G), and H = G− {v}. Then
dens(G) < dens(H) ⇐⇒ deg(v) < dens(G).
Proof. Note that |E(H)| = |E(G)| − deg(v) and |V (H)| = |V (G)| − 1. Let |E(G)| =
E, |V (G)| = V,deg(v) = d.
dens(G) < dens(H) ⇐⇒
E
V−1 <
E−d
V−2 ⇐⇒
EV − 2E < EV − dV − E + d ⇐⇒
d(V − 1) < E ⇐⇒
d < EV−1 = dens(G).
M. O. Albertson et al.: More results on r-inflated graphs. . . 9
Theorem 3.5. A maximum density subgraph of G[r], which is vertex maximal with that
property, is the r-inflation of a subgraph of G.
Proof. The conclusion is immediate if G[r] is uniformly dense. Suppose G[r] = G is not
uniformly dense. Choose any vertex maximal subgraphH of G with maximal density. Note
that since H has maximal density it is necessarily an induced subgraph of G. We call two
vertices v, u of G siblings if they are in the inflation of the same vertex of G. To prove the
theorem it is sufficient to show that if v ∈ V (G) is not in V (H) then no sibling of v is in
V (H).
Let V (G) − V (H) = {v1, . . . , vk}. Define G0 = G and for all i = 1, . . . , k, Gi =
Gi−1−{vi}. SinceH is an induced subgraph of G with the same vertex set as Gk, Gk = H.
Suppose that there exists j so that vj has a sibling v′j that is in V (H). Without loss of
generality, we may assume that j = k (or we could reorder the vi). Notice that siblings
have the same degree and the same set of neighbors in G. For each vi removed in getting
toH, vi is either a neighbor of both vk and v′k or of neither. Thus the degrees of vk, v′k are
the same in each of G, . . . ,Gk−1. In Gk, vk is removed but v′k is not. Hence the degree of
vk in Gk−1 is one more than the degree of v′k in Gk.
By the hypothesis on H, dens(H) = dens(Gk) > dens(Gk−1) (otherwise we would
have chosen Gk−1 instead of Gk = H). By Lemma 3.4 this means that degGk−1(vk) <
dens(Gk−1) < dens(Gk). But since we have degGk(v
′
k) < degGk−1(vk) this means that
degGk(v
′
k) < dens(Gk).
Thus by Lemma 3.4, dens(H−{v′k}) > dens(H), which is impossible since we chose
H to have maximal density.
Thus if v ∈ V (G) is not in V (H) then no sibling of v is in V (H). In particular if
v ∈ V (H) then all siblings of v are in V (H). Thus H is the r-inflation of the induced
subgraph of G obtained by deleting from G the vertices corresponding to the Krs deleted
from G to yieldH.
Theorem 3.6. If a connected graph G has uniform density then so does G[r].
Proof. Assume that G is connected and uniformly dense. Let |E(G)| = E and |V (G)| =
V . It is not hard to show that if we remove k vertices and ` edges from graph G to obtain
H , then EV−1 <
E−`
V−1−k ⇐⇒
`
k <
E
V−1 . Thus since G is uniformly dense, for all ` edges
and k vertices whose removal from G results in a subgraph, EV−1 = dens(G) ≤
`
k .
Let H be a subgraph of G and let us compare the density of H[r] with G[r]. Note that
if we remove k vertices and ` edges from G to obtain H , then we remove rk vertices and(
r
2
)
k + r2` edges from G[r] to obtain H[r]. Then dens(H[r]) ≤ dens(G[r]) if and only if(
r
2
)
k + r2`
rk
≥
(
r
2
)
V + r2E
rV − 1
⇐⇒(
r
2
)
rkV + r3`V −
(
r
2
)
k − r2` ≥
(
r
2
)
rkV + r3kE ⇐⇒
`(r3V − r2) ≥ k
(
r3E +
(
r
2
))
⇐⇒
10 Ars Math. Contemp. 4 (2011) 5–24
`
k
≥
r3E +
(
r
2
)
r3V − r2
.
Let A =
r3E+(r2)
r3V−r2 and let us compare A to dens(G) =
E
V−1 .
A ≤ dens(G) ⇐⇒
r3E +
(
r
2
)
r3V − r2
≤ E
V − 1
⇐⇒
r3EV +
(
r
2
)
V − r3E −
(
r
2
)
≤ r3V E − r2E ⇐⇒
(V − 1)
(
r
2
)
≤ E(r3 − r2) ⇐⇒(
r
2
)
r3 − r2
=
1
2r
≤ E
V − 1
,
which is exact since G is connected and therefore contains at least V − 1 edges. Thus
A ≤ dens(G).
Since G is uniformly dense, if we remove k vertices and ` edges from G to obtain H
then A ≤ dens(G) ≤ `k which implies that dens(H[r]) ≤ dens(G[r]). Since by Theorem
3.5, one subgraph ofG[r] for which maximal density occurs is the r-inflation of a subgraph
ofG, no other subgraph ofG[r] has density larger than that ofG[r]. ThusG[r] is uniformly
dense.
4 Thickness
There are two primary tools we use in evaluating the thickness of an inflated graph. The
first is a theorem that gives us an upper bound on the thickness of an r-inflation.
Theorem 4.1. [2] If the arboricity of G is k then the thickness of G[r] is at most k
⌈
r
2
⌉
.
To find a lower bound on Θ(G[r]) we can take the ceiling of the number of edges of
G[r] divided by the maximum possible number of edges in a planar layer of G[r]. We call
this the edge counting bound. In those instances where the two bounds meet, they provide
the thickness of G[r].
As mentioned in [2], it is easy to check that the clone of any cycle contains a K5
subdivision and thus has thickness two. What about the thickness of other vertex transitive
graphs?
Theorem 4.2. Let G be a vertex transitive graph of degree d ≥ 3 on n vertices. Then⌈
2d+ 1
6
(
n
n− 1
)⌉
≤ Θ(G[2]) ≤
⌈
d
2
(
n
n− 1
)⌉
.
Proof. G has n vertices and dn2 edges. SinceG is vertex transitive, it is uniformly dense and
therefore its arboricity is the ceiling of its density. Thus arb(G) =
⌈
dn
2
n−1
⌉
=
⌈
d
2
(
n
n−1
)⌉
.
Thus by Theorem 4.1, the thickness of G[2] is at most
⌈
d
2
(
n
n−1
)⌉
.
M. O. Albertson et al.: More results on r-inflated graphs. . . 11
By Observation 1 compute that G[2] has 2n vertices and n + 2dn edges. Thus using
the edge counting bound, a lower bound on the thickness of G[2] is given by
⌈
n+2dn
6n−6
⌉
=⌈
2d+1
6
(
n
n−1
)⌉
.
Note that except for small n, the value of nn−1 is close enough to 1 to not make a
difference in the value of the ceiling, except to bump up the value if 2d+16 or
d
2 is an
integer.
The difference between these bounds is approximately
(
d
2 −
2d+1
6
) (
n
n−1
)
= d−12(
n
n−1
)
(found by ignoring the ceiling function and simply subtracting). Thus the difference
between these bounds grows as the degree grows.
Corollary 4.3. The clone of a vertex transitive graph of degree 3 has thickness two.
5 Chromatic number
Definition 5.1. Given integers k, r and a graph G, a kr -coloring of G is an assignment of
subsets of size r from {1, . . . , k} so that subsets assigned to adjacent vertices are disjoint.
The fractional chromatic number of G, denoted χf (G), is inf{kr | there is a
k
r -coloring of
G}.
Since a proper n-coloring is an n1 -coloring, it is immediate that χf (G) ≤ χ(G).
Theorem 5.2. [40] For any graph G, χf (G) ≥ |V (G)|α(G) with equality guaranteed when G is
vertex transitive.
Thus we have r|V (G)|α ≤ χfG[r] ≤ χ(G[r]) ≤ rχ(G). Note that a
k
r -coloring ofG can
be identified with k-coloring ofG[r]. In particular, we can set up a correspondence between
the list of colors assigned to a vertex v in a fractional coloring of G and the colors used
in coloring the vertices of v[r] in a proper coloring of G[r]. This correspondence shows
that G is kd -colorable if and only if the d-inflation of G is k-colorable. Thus an alternate
definition for fractional chromatic number is: χf (G) = inf{ kd | G[d] is k-colorable}.
6 Results in chosen graph families
In this section we use the tools developed in previous sections to learn about the arboricity,
thickness, chromatic number, and fractional chromatic number of the r-inflation of certain
graphs or families of graphs.
Note that in many of the computations below we take a complicated-looking bound on
a parameter for an r-inflation of a graph on n vertices and write it as a simpler bound that
for each r is achieved for all but a finite number of small n (sometimes except for only
trivially small n). In the summary table given in the following section we use these simpler
bounds, followed by an asterisk ∗, to indicate that some small differences may occur for
small graphs.
12 Ars Math. Contemp. 4 (2011) 5–24
6.1 Icosahedral graph
Let I be the icosahedral graph. By Observation 1, since I has 12 vertices and 30 edges,
I[r] has 12r vertices and 12
(
r
2
)
+ 30r2 = 36r2 − 6r edges.
Arboricity: By Observation 7, since I is vertex transitive so is I[r]. By Theorem
3.2 since I[r] is connected and vertex transitive, it has uniform density and therefore
arb(I[r]) =
⌈
36r2−6r
12r−1
⌉
=
⌈
3r − 14 −
1
48r−4
⌉
= 3r.
Thickness: In [2] we proved that the thickness of I[r] is precisely r.
Chromatic Number: In [2] we proved that the chromatic number of I[r] is 4r. Since
I is vertex transitive with independence number 3, so is I[r]. Thus by Theorem 5.2,
χf (I[r]) =
12r
3 = 4r as well.
6.2 Dodecahedral graph
Let D be the dodecahedral graph. By Observation 1, since D has 20 vertices and 30 edges
D[r] has 20r vertices and 20
(
r
2
)
+ 30r2 = 40r2 − 10r edges.
Arboricity: By Observation 7, since D is vertex transitive so is D[r]. By Theorem 3.2,
since D[r] is connected and vertex transitive, it follows that arb(D[r]) =
⌈
40r2−10r
20r−1
⌉
=⌈
2r − 25 −
2
100r−5
⌉
= 2r.
Thickness: In [24] it was shown that the clone of the dodecahedral graph has thickness
two. By Theorem 4.1, since D has arboricity 2 (an easy decomposition into a Hamiltonian
path and its complement), the thickness of D[r] is at most 2
⌈
r
2
⌉
. On the other hand, the
edge counting bound tells us that the thickness of D[r] is at least
⌈
2
3r −
1
10 −
1
100r−10
⌉
=⌈
2r
3
⌉
. Thus
⌈
2r
3
⌉
≤ Θ(D[r]) ≤ 2
⌈
r
2
⌉
.
Chromatic Number: By Theorem 5.2, since D[r] is vertex transitive χf (D[r]) =
20r
8 =
5
2r and thus
5r
2 is a lower bound for χ(D[r]). In particular, 5 = χf (D[2]) ≤
χ(D[2]). However, χf (D) = 52 (again by Theorem 5.2). By our observation in Section 5,
a 52 -fractional coloring of D corresponds to a proper 5-coloring of D[2]. Thus 5 is also
an upper bound on the chromatic number and hence χ(D[2]) = 5. Suppose that r is
even. By Observation 2 if we let H = D[2] then H[ r2 ] = D[r]. By Observation 5,
χ(D[r]) = χ(H[ r2 ]) ≤
r
2χ(H) =
r
2χ(D[2]) =
5r
2 . Thus when r is even,
5r
2 also provides
an upper bound and therefore χ(D[r]) = 5r2 .
6.3 Trees
By Observation 1, since a tree T on n vertices has n − 1 edges, T [r] has rn vertices and(
r
2
)
n+ r2(n− 1) = 32r
2n− 12rn− r
2 edges.
Arboricity: By Theorem 3.3, trees are uniformly dense. By Theorem 3.6, since a
tree T is connected, T [r] is uniformly dense. Thus arb(T [r]) =
⌈
3
2 r
2n− 12 rn−r
2
rn−1
⌉
=⌈
3
2r −
1
2 −
2r2−3r+1
2rn−2
⌉
. For a given r, for all but finitely many small n, this quantity is
equal to
⌈
3r−1
2
⌉
.
M. O. Albertson et al.: More results on r-inflated graphs. . . 13
Thickness: We showed in [2] that the thickness of T [r] is at most
⌈
r
2
⌉
and for all but
finitely many trees, equality holds. For completeness, we show that computation here. The
edge counting bound for Θ(T [r]) yields Θ(T [r]) ≥
⌈
1
2r −
1
6 −
r2−3r+1
3rn−6
⌉
. For a given
value of r, for all but a finite number of small n, this is
⌈
r
2
⌉
. Thus for each r we have
Θ(T [r]) =
⌈
r
2
⌉
for all but a finite number of small n.
Chromatic Number: By Observation 4, since ω(T ) = 2, ω(T [r]) = 2r. This implies
that χ(T [r]) ≥ 2r. However, by Observation 5, since χ(T ) = 2, χ(T [r]) ≤ 2r and thus
χ(T [r]) = 2r.
6.4 Maximal planar graphs
Let G be a maximal planar graph on n vertices. By Observation 1, since a maximal planar
graph on n vertices has 3n − 6 edges, G[r] has rn vertices and
(
r
2
)
n + r2(3n − 6) =
7
2r
2n− 12rn− 6r
2 edges.
Arboricity: By Theorem 3.3, a maximal planar graph G is uniformly dense. By The-
orem 3.6 since a maximal planar graph is connected, this tells us that G[r] is uniformly
dense. Thus arb(G[r]) =
⌈
7
2 r
2n− 12 rn−6r
2
rn−1
⌉
=
⌈
7
2r −
1
2 −
6r2− 72 r+
1
2
rn−1
⌉
. For each r, for all
but a finite number of small n, this quantity is equal to
⌈
7r−1
2
⌉
.
Thickness: By Theorem 4.1, since the arboricity of G is at most 3, Θ(G[r]) ≤ 3
⌈
r
2
⌉
.
On the other hand, using the edge counting bound we get
Θ(G[r]) ≥
⌈
7
6
r − 1
6
− 6r
2 − 7r + 1
3rn− 6
⌉
.
For each r, for all but a finite number of small n, this is
⌈
7r−1
6
⌉
. Thus, for each r, for all
but a finite number of small n,
⌈
7r−1
6
⌉
≤ Θ(G[r]) ≤ 3
⌈
r
2
⌉
.
Chromatic Number: By the Four Color Theorem, χ(G) ≤ 4. By Observation 5,
χ(G[r]) ≤ 4r.
6.5 Cycles
By Observation 1, since Cn has n vertices and n edges, Cn[r] has rn vertices and
(
r
2
)
n +
r2n = 32r
2n− 12rn edges.
Arboricity: By Observation 7, since Cn is vertex transitive, so is Cn[r]. By The-
orem 3.2, since Cn[r] is connected and vertex transitive, it is uniformly dense. Thus
arb(Cn[r]) =
⌈
3
2 r
2n− 12 rn
rn−1
⌉
=
⌈(
3
2r −
1
2
) (
rn
rn−1
)⌉
. By studying the cases when r is
even and when r is odd, we can see that, for all but trivially small n, this is
⌊
3r+1
2
⌋
.
Thickness: A cycleCn is the union of a path on n vertices, Pn, and an edge e. Since Pn
is a tree, by the results in Section 6.3 (and by Proposition 4 in [2]), we have Θ(Pn[r]) = d r2e
for all but finitely many small values of n. The edge e, when r-inflated, gives rise to a Kr,r
which by [10], has thickness b r+54 c. Since Cn[r] is the disjoint union of Pn[r] and Kr,r we
have Θ(Cn[r]) ≤ d r2e + b
r+5
4 c. When r is even, this quantity reduces to b
3r+5
4 c; when r
is odd, it reduces to b 3r+74 c.
14 Ars Math. Contemp. 4 (2011) 5–24
On the other hand, the edge counting bound yields Θ(Cn[r]) ≥
⌈
3
2 r
2n− 12 rn
3rn−6
⌉
=⌈
1
2r −
1
6 +
3r−1
3rn−6
⌉
. For all but a few small values of n this is equal to
⌈
r
2
⌉
. Thus r2 ≤
Θ(Cn[r]) ≤ b 3r+54 c when r is even and
⌈
r
2
⌉
≤ Θ(Cn[r]) ≤ b 3r+74 c when r is odd. As
previously mentioned, for all n, Θ(Cn[2]) = 2. Thus when r = 2, the upper bound is
achieved.
Chromatic Number: By [12, 19], χ(C2k+1[r]) = 2r + d rk e. Thus, for a given r, for
all but a finite number of small k, χ(C2k+1[r]) = 2r + 1. By Theorem 5.2, since Cn[r] is
vertex transitive, χf (C2k+1[r]) =
|V (C2k+1[r])|
α(C2k+1[r])
= r(2k+1)k = 2r+
r
k . Analogous reasoning
shows that χ(C2k[r]) = 2r and χf (C2k[r]) = 2r.
6.6 Wheels
The n-wheel Wn is the join of Cn and a single vertex. By Observation 1, since Wn has
n+ 1 vertices and 2n edges Wn[r] has rn+ r vertices and
(
r
2
)
(n+ 1) + 2r2n = 52r
2n−
1
2rn+
1
2r
2 − 12r edges.
Arboricity: By Theorem 3.6, since Wn is connected and uniformly dense so is Wn[r].
Thus arb(Wn[r]) =
⌈
5
2 r
2n− 12 rn+
1
2 r
2− 12 r
rn+r−1
⌉
=
⌈
5
2r −
1
2 −
2r2− 52 r+
1
2
rn+r−1
⌉
. For a given r, for
all but finitely many small n, this is
⌈
5r−1
2
⌉
.
Thickness: By Theorem 4.1, since Wn has arboricity two Θ(Wn[r]) ≤ 2
⌈
r
2
⌉
. On the
other hand, the edge counting bound yields Θ(Wn[r]) ≥
⌈
5
6r −
1
6 −
2r2−5r+1
3rn+3r−6
⌉
. For a
given r for all but a finitely many small n this is equal to
⌈
5r−1
6
⌉
. Thus for a given r, for
all but finitely many small n,
⌈
5r−1
6
⌉
≤ Θ(Wn[r]) ≤ 2
⌈
r
2
⌉
.
Chromatic Number: Since Wn is the join of Cn and K1, Wn[r] is the join of Cn[r]
and K1[r] = Kr. Thus χ(Wn[r]) = χ(Cn[r]) + χ(Kr). That is,
χ(Wn[r]) =
{
3r +
⌈
r
k
⌉
if n = 2k + 1
3r if n = 2k
.
By Theorem 5.2, χf (W2k+1[r]) ≥ 2r + 2rk and χf (W2k[r]) ≥ 2r +
r
k .
6.7 Generalized series parallel graphs
In [2] it was shown that the arboricity of an outerplanar graph G is at most two, and hence
the thickness of its clone, G[2], is at most two as well. Toward the goal of understanding
which planar graphs G satisfy Θ(G[2]) = 2, we move one step away from outerplanar
graphs to the generalized series parallel graphs or GSP graphs. Series parallel graphs (or
SP graphs) have their roots in electrical networks of the same name; see, for example, [15].
The advantage of studying GSP graphs over SP graphs is that the former class is broader
and contains the outerplanar graphs [34].
Definition 6.1. A graph G is a GSP graph if it can be reduced to K2 through any sequence
of the operations below. A graph G is an SP graph if it can be reduced to K2 using only
the first two operations.
1. Remove a parallel edge.
M. O. Albertson et al.: More results on r-inflated graphs. . . 15
2. Replace an edge subdivided by a vertex with a single edge (i.e., suppress a vertex of
degree 2)
3. Delete a vertex of degree 1.
The 2-connected SP graphs are precisely the 2-connected graphs with no K4 mi-
nor [14]. The SP graphs are precisely those graphs with treewidth at most two [17, 16].
Some consequences are as follows. Let G be a simple GSP graph on n vertices. Then G
is connected and planar with at most 2n − 3 edges. By definition, G must have a vertex
of degree 2 or less. The latter implies that the maximum chromatic number of any GSP
graph is 3. Finally, K2,n for all n ≥ 3 are GSP graphs, none of which are outerplanar.
Thus GSP graphs may be viewed as a class of planar graphs that lie somewhere between
outerplanar and arbitrary planar graphs. We show that the clone of any simple GSP graph
has thickness at most two, and in general, that the r-inflation of any simple GSP graph has
thickness at most 2
⌈
r
2e . We do so by first computing the arboricity of any GSP graph.
Arboricity:
Lemma 6.2. Let G be a simple GSP graph. Then arb(G) ≤ 2.
Proof. Assume by induction that all simple GSP graphs on k or fewer vertices have ar-
boricity at most two and suppose G is a simple GSP graph on k + 1 vertices. Without loss
of generality, assume G is not a tree; thus it has arboricity at least two. It remains to show
that G has arboricity exactly two. One can show directly from the definition that every
GSP graph has at least one vertex of degree two or less. Choose such a vertex v. If v has
degree 2, then replace the edge that v subdivides with a single edge e (operation 2 in Def-
inition 6.1) and if e is a parallel edge, remove it also (operation 1 in Definition 6.1). Call
the new graph G′. By construction, G′ is a simple GSP graph on k vertices, and hence by
induction has arboricity at most two. If arb(G′) = 2, it is straightforward to return v and
its two incident edges to the forest decomposition while maintaining the arboricity of G′
by adding one pendant edge to each of the two forests. On the other hand, if arb(G′) = 1,
add v and one pendant edge to the forest G′, and consider v and the remaining pendant
edge as a second forest. Thus in either case arb(G) = arb(G′) = 2. Finally, if G has no
vertex of degree two, it must have some vertex of degree 1; let v be such a vertex. Deleting
v from G yields a simple GSP graph G′ (operation 3 in Definition 6.1) that, by induction,
has arboricity exactly 2 (since we have assumed that G is not a tree). As before, return the
pendant edge with v as an endpoint to either forest in the arboricity two decomposition of
G′; thus arb(G′) = arb(G) = 2. By induction, then, simple GSP graphs have arboricity
at most two.
Because any GSP graph on n vertices has at most 2n − 3 edges, and d 2n−3n−1 e =
d2− 1n−1e = 2, Nash-Williams [36] together with Lemma 6.2 imply that any GSP graph
G is uniformly dense. In that case, by Theorem 3.6, G[r] is uniformly dense as well. Since
the number of edges in G[r] is bounded above by n
(
r
2
)
+ r2(2n − 3) (Observation 1) we
have that the arboricity of G[r] is bounded above by d 5r
2n−rn−6r2
2rn−2 e. For a fixed r, and for
all but finitely many n, this quantity is exactly d 5r−12 e.
Thickness: Using Lemma 6.2 we bound the thickness of the clone and of the r-inflation
of a GSP graph.
16 Ars Math. Contemp. 4 (2011) 5–24
Corollary 6.3. Let G be a simple GSP graph. Then the thickness of G[2] is at most two.
Proof. The result follows directly from Theorem 4.1 that the thickness of the clone of a
graph is at most its arboricity.
Corollary 6.4. Let G be a simple GSP graph. Then the thickness of G[r] is at most 2
⌈
r
2e .
Proof. The result follows directly from Theorem 4.1 and Lemma 6.2.
Chromatic Number: As previously mentioned, a GSP graph G always has a vertex of
degree two or less and thus by induction, χ(G) ≤ 3. It then follows from Observation 5
that χ(G[r]) ≤ 3r.
6.8 Planar undirected circulant graphs
Finally we turn our attention to the clones and r-inflations of planar undirected circulant
graphs. The motivation for considering these particular graphs is that a large class of them
have arboricity three but their clones have thickness two. We begin with the definition of
circulant graph and use the notation and some of the results in [26].
Definition 6.5. Let {a1, a2, . . . , am} a set of m positive integers, with m ≥ 1. Suppose
G is a graph on n vertices V (G) = {0, 1, . . . , n − 1}, with edges given by E(G) =
{(i, i + aj) : 0 ≤ i ≤ n − 1, 1 ≤ j ≤ m}. Then G is called a circulant graph and is
denoted by Cn(a1, a2, . . . , am).
The study of circulant graphs, those graphs whose adjacency matrices are circulants,
began in the late 1960s: see, for example [1, 18, 4]. In 2003, C. Heuberger completely
characterized planar undirected circulant graphs; we use this characterization to prove that
the clone of any planar circulant graph has thickness two; in addition, we provide upper
and lower bounds on the the thickness of the r-inflation of these graphs. Note that when
m = 1 it is easy to show that Cn(a1) is either a cycle or else a disjoint union of cycles;
either way, when G = Cn(a) for some positive integer a, the clone of G has thickness
two. Thus the interesting cases occur when m ≥ 2. Before stating the results in [26], we
mention a few preliminary well known facts about circulant graphs.
Remarks:
Let G = Cn(a1, a2, . . . , am) be a circulant graph.
1. Then G is connected if and only if gcd(a1, a2, . . . , am) = 1.
2. If G is disconnected, then its components are mutually isomorphic.
3. G is regular of degree δ, where
δ =
{
2m, if aj 6≡ n2 (mod n) for all 1 ≤ j ≤ m
2m− 1, otherwise
(6.1)
4. G is vertex transitive.
One more definition is needed before stating the required result from [26].
M. O. Albertson et al.: More results on r-inflated graphs. . . 17
Definition 6.6. Let p be prime and suppose k ∈ Z. Then the p-adic valuation of k , written
vp(k), is the largest integer ` such that p`|k.
Theorem 6.7. [26] Let G = Cn(a1, a2, . . . , am) be a circulant graph.
1. If m ≥ 3 then G is non-planar.
2. Suppose m = 2 and consider G = Cn(a1, a2). Then G is planar if and only if one
of the following two conditions is satisfied:
(a) ai ≡ ±2aj (mod n) and v2(aj) < v2(n), where (i, j) = (1, 2) or (2, 1)
(b) ai = n2 and 1 ≤ v2(n) ≤ v2(aj), where (i, j) = (1, 2) or (2, 1)
We now have most of the tools needed to do an analysis of planar undirected circulant
graphs on an even number of vertices.
Arboricity: Let G = C2n(1, 2), n ≥ 2; then G is 4-regular with 4n edges. Since G
is vertex transitive, it is uniformly dense and hence arb(G) =
⌈
4n
2n−1e = 3. By Observa-
tion 7, G[r] is vertex transitive and by Observation 1 has 2nr vertices and nr2−nr+4r2n
edges. Hence for a fixed value of r, we have arb(G[r]) =
⌈
5r2n−nr
2nr−1 e =
⌈
5r−1
2 e for all
but finitely many values of n.
Thickness: Like the icosahedral graph whose arboricity is three and whose clone has
thickness two, we find that the even planar 4-regular circulant graphs provide an infinite
family of graphs whose arboricity does not give the best bound for the thickness of their
clones.
Theorem 6.8. Let G = C2n(a1, a2) be a planar undirected circulant graph on an even
number of vertices. Then the thickness of G[2] is two.
Proof. As mentioned earlier, when m = 1, for all a, n ∈ Z+, the clone of Cn(a) has
thickness two. As shown in [26], whenm ≥ 3, the undirected circulantCn(a1, a2, . . . , am)
is not planar. Furthermore, by Remarks 1 and 2, since a disconnected circulant graph has
mutually isomorphic components, it suffices to consider only planar circulants C2n(a1, a2)
with gcd(a1, a2) = 1. In case (b), by Remarks 3 and 4, since G = C2n(a1, a2) is vertex
transitive of degree three, Corollary 4.3 implies that G[2] has thickness two regardless of
whether or not the graph C2n(n2 , a2) is planar.
Thus it remains to show that a planar circulant graph G satisfying condition (a) of
Theorem 6.7 (as proved in [26]), when cloned, has thickness two. To this end, as noted
in [26], we use the following straightforward observation: If G = C2n(a1, a2) with
gcd(a1, 2n) = 1, then G is isomorphic to C2n(1, a1−1a2 (mod 2n)), where the roles
of a1 and a2 can be interchanged.
In particular, observe that since gcd(a1, a2, 2n) = 1 and a1 ≡ ±2a2 (mod 2n), we
have gcd(±2a2 + 2kn, a2, 2n) = 1 for some k ∈ Z. Thus gcd(a2, 2n) = 1, in which case
C2n(±2a2 (mod 2n), a2) is isomorphic to C2n(1, a−12 (±2a2 (mod 2n))) = C2n(1,±2
(mod 2n)). Notice that the 2-adic valuation criteria in Theorem 6.7(a) is trivially satisfied
since 2n is even and a2 is odd. The planar circulant graph families that we must consider
are C2n(1, 2) and C2n(1, 2n − 2), which are identical for each fixed value of n. Thus the
problem is reduced to showing that for any n ∈ Z+ the clone of the planar circulant graph
18 Ars Math. Contemp. 4 (2011) 5–24
C2n(1, 2) has thickness two. In this case, since C2n(1, 2) has 4n edges, the arboricity is
larger than two, and hence we must use an alternative method to show that its clone has
thickness two.
To complete the last part of the proof, note that a plane drawing of C2n(1, 2) can be
accomplished by embedding two plane drawings of Cn, one inside the bounded region
of the other, and then drawing in a Hamiltonian cycle by alternating vertices from the
two copies of Cn. We alter the standard vertex labeling of C2n(1, 2) to better suit the
given plane embedding. Specifically, if the vertices of the inner Cn are labeled, in order,
0, 1, . . . , n− 1 and the vertices of the outer Cn are labeled, in order, n, n+ 1, . . . , 2n− 1,
then we use the Hamiltonian cycle given by 0, n, 1, n + 1, 2, n + 2, . . . , i, n + i, . . . , n −
1, 2n−1, 0. Figure 1 shows such a plane drawing ofC10(1, 2), where the bold edges display
a perfect matching of C10(1, 2). In general, the edges
{mi = (i, i+ n) : 0 ≤ i ≤ n− 1} (6.2)
yield a perfect matching of C2n(1, 2), the fact of which is needed in the remainder of the
proof. The vertex labeling scheme for cloning a graph G on 2n vertices is as follows:
0
1
2 3
4
5
6
7 8
9
Figure 1: The graph G = C10(1, 2) and a plane embedding; the vertices on the right are
labeled to facilitate the proof of Theorem 6.8. The bold edges constitute a perfect matching
of G. The highlighted region illustrates the unique quadrilateral associated with matching
edge (0, 5).
a vertex labeled i in G is replaced by a pair of vertices i and i + 2n in G[2] for i =
0, . . . , 2n − 1. Specifically, vertices i and i + 2n induce a K2 in G[2] and are called
siblings in keeping with the terminology used in Theorem 3.5. Moreover, by Observation 6,
an edge of G induces a K4 in G[2]; a K4 is an edge-disjoint union of two paths of length
three. Let us focus on the perfect matching edges mi of C2n(1, 2) as given in (6.2). First,
each matching edge mi = (i, i+ n) in G uniquely determines a quadrilateral, namely, the
one given by i, i+ 1 (mod n), i+ n, and i− 1 + n for i = 0, . . . , n− 1. Each matching
edge mi in G induces a K4 in G[2] by way of the vertices i, i + 2n, i + n, and i + 3n.
Decompose each such K4 into two paths of length three: P1(i) = i, i + 2n, i + 3n, i + n
and P2(i) = i+ 2n, i+n, i, i+ 3n. The paths are edge disjoint, and P1(i)∪P2(i) induces
a K4. See Figure 2.
Now subdivide every mi by two vertices; each such subdivided edge induces a path of
length three. Note that subdividing an edge does not alter the genus of a graph. Next add
edges from vertices i+ 1 and i−1 +n to the two subdivision vertices for i = 0, . . . , n−1;
call the new graph G′. By construction G′ is planar. Make two copies of G′ and call
them G1[2] and G2[2]. Label the vertices in G1[2] by maintaining the labeling of G and
then labeling the subdivision vertices of matching edge mi to yield the path P1(i) for
M. O. Albertson et al.: More results on r-inflated graphs. . . 19
=
i+n
i
cloned
i+n
i
i+3n
i+2n
i+n
i+3n
i+2n
i
Ü
i+3n
i
i+n
i+2n
matching edge
mi K4 P1HiL P2HiL
Figure 2: Decomposition of cloned matching edge mi into paths P1(i) and P2(i).
i = 0, . . . , n − 1. Label the vertices in G2[2] by replacing the vertices from the original
labeling of G with their siblings. Then effect P2(i) on the subdivision vertices of each
matching edge mi. The placement of the subdivision labels in each of G1[2] and G2[2] is
unambiguous since the labels of the endpoints of the subdivided edges are given initially.
See Figure 3.
i+1 i i-1
i+1+n i+n i-1+n
i+2n
i+3n
i+1+2n
i+1+3n
i-1+2n
i-1+3n
fragment of G1@2D
i+1+2n i+2n i-1+2n
i+1+3n i+3n i-1+3n
i+n
i
i+1+n
i+1
i-1+n
i+1
fragment of G2@2D
Figure 3: Fragments of the graphs G1[2] and G2[2].
It suffices to show that G[2] ⊂ G1[2] ∪ G2[2]. Alternatively, if NH(x) denotes the
neighborhood of vertex x in graph H , then it is enough to show that it holds NG[2](i) ⊂
NG1[2]∪G2[2](i). To this end, suppose i is an arbitrary vertex in G and let 0 ≤ i ≤ n − 1.
Recall thatG is 4-regular and observe thatNG(i) = {i−1, i+1, i+n, i−1+n}. Therefore,
NG[2](i) = {i−1, i+ 1, i+n, i−1 +n, i+ 2n, i−1 + 2n, i+ 1 + 2n, i+ 3n, i−1 + 3n}.
By construction, NG1[2](i) = {i+ 1, i+ 2n, i− 1, i− 1 + 2n, i− 1 + 3n, i− 1 + n} and
NG2[2](i) = {i− 1 + 3n, i+ 3n, i+ n, i+ 1 + 2n} and thus NG[2](i) ⊂ NG1[2]∪G2[2](i),
as desired. Notice that edge (i, i − 1 + 3n) appears in both of NG1[2](i) and NG2[2](i),
which means that G1[2]∪G2[2] is not simple, but this fact is not relevant to the discussion
at hand: in a thickness-two decomposition of G = C2n(1, 2) one could simply remove the
edges {(i, i−1+3n) : i = 0, . . . , n−1} fromG1[2]. Finally, the same method can be used
to show that any vertex x in G[2] satisfies NG[2](x) ⊂ NG1[2]∪G2[2](x) and this completes
the proof.
Example. An edge decomposition of G = C10(1, 2) by way of G1[2] and G2[2] is given
in Figure 4. Note that the multiple edges have been retained.
The same technique, together with the lemma below as detailed in [2] can be modified
to prove the following theorem:
Theorem 6.9. The thickness of the r-inflation of C2n(1, 2) is at most r.
20 Ars Math. Contemp. 4 (2011) 5–24
0
1
2 3
4
5
6
7 8
9
10
15
14 19
13
18
12
17
1116
G1@2D
10
11
12 13
14
15
16
17 18
19
5
0
9 4
8
3
7
2
61
G2@2D
Figure 4: G = C10(1, 2) is contained in G1[2] ∪G2[2].
We omit the lengthy proof here, but the key ideas are contained in the proof of Theo-
rem 6.8 and Section 4 of [2]. In particular, any edge from a graph G becomes a K2r in
G[r]. Further K2r is an edge disjoint union of r Hamiltonian paths of length 2r − 1. For
example, in the proof of Theorem 6.8, matching edges became paths of length three in each
of the two planar layers, and the union of corresponding paths of length three induced aK4.
That idea, together with the lemma below, is at the core of the construction for the general
case.
Lemma 6.10. LetK2r be a complete graph on 2r vertices with vertices labeled v1,. . . , v2r.
The edges of K2r can be partitioned into r Hamiltonian paths, P1, P2, . . . , Pr, each with
one endpoint in {v1, v2, . . . , vr} and the other in {vr+1, vr+2, . . . , v2r}.
Finally, since the number of edges in G[r] is 5r2n − rn and the number of vertices
is 2rn, the edge counting bound tells us that for a given fixed r, we have Θ(G[r]) ≥
d 5r
2n−rn
6rn−6 e = d
5r−1
6 e for all but finitely many values of n.
Chromatic Number: The planar circulant graphs of degree four are the most inter-
esting of the family of planar circulant graphs. It turns out that the chromatic number
of the clone of any such graph can be determined up to a point. By construction, the
independence number of C2n(1, 2) is roughly 13 of the number of vertices in C2n(1, 2)
and in particular α(C2n(1, 2)) =
⌊
2n
3 c When 3|n, χ(C2n(1, 2)) = 3 in which case,
χ(C2n(1, 2)[2]) ≤ 6 by Observation 5. On the other hand, since the clique number of
C2n(1, 2) is 3, by Observation 4, the clique number of C2n(1, 2)[2] is six, and hence
χ(C2n(1, 2)[2]) ≥ 6. Altogether χ(C2n(1, 2)[2]) = 6. When 3 does not divide n,
χ(C2n(1, 2)[2]) = 4 [26], which means, by Observation 5, χ(C2n(1, 2)[2]) ≤ 8. On
the other hand, χ(C2n(1, 2)[2])≥ 4nb 2n3 c >
4n
2n
3
= 6 and thus χ(C2n(1, 2)) ∈ {7, 8}. Exper-
imental evidence shows that χ = 8 does occur, so the upper bound is achieved. Similarly,
when 3|n, we have χ(C2n(1, 2)[r]) = 3r and otherwise χ(C2n[r]) ∈ (3r, 4r]. Finally, by
Observation 3, since C2n(1, 2) has independence number α = b 2n3 c, so does C2n(1, 2)[r].
Thus χf (C2n(1, 2)[r]) = 2nrb 2n3 c
.
M. O. Albertson et al.: More results on r-inflated graphs. . . 21
7 Summary table
See Table 1 for a summary of the results found in Section 6. In this table, ∗ indicates that
for each r the value is exact for all but a finite number of small graphs.
Arboricity Thickness χ χf
Icos. Graph 3 1 4 4
Cloned 6 2 8 8
r-Inflated 3r r 4r 4r
Dodec. Graph 2 1 3 5
2
cloned 4 2 5 5
r-Inflated 2r
⌈
2r
3
⌉
≤ Θ ≤ 2d r
2
e 5r
2
for even r 5
2
r
Tree 1 1 2
cloned 3 1 4
r-inflated
⌈
3r−1
2
⌉∗ d r
2
e∗ 2r
Maximal Planar 3∗ 1 ≤ 4
cloned 7∗ 3∗ ≤ 8
r-inflated
⌈
7r−1
2
⌉∗ ⌈ 7r−1
6
⌉∗ ≤ Θ ≤ 3 ⌈ r
2
⌉
≤ 4r
Even Cycle C2k 2 1 2 2
cloned 3∗ 2 4 4
r-Inflated
⌊
3r+1
2
⌋∗ ⌈ r
2
⌉∗ ≤ Θ ≤ ⌈ r
2
⌉
+
⌊
r+5
4
⌋
2r 2r
Odd Cycle C2k+1 2 1 3 2 + 1k
cloned 3∗ 2 5∗ 4 + 2
k
r-Inflated
⌊
3r+1
2
⌋∗ ⌈ r
2
⌉∗ ≤ Θ ≤ ⌈ r
2
⌉
+
⌊
r+5
4
⌋
2r + 1∗ 2r + r
k
Even Wheel W2k 2 1 3 ≥ 2 + 1k
cloned 5∗ 2 6 ≥ 4 + 2
k
r-Inflated
⌈
5r−1
2
∗⌉ ⌈ 5r−1
6
⌉∗ ≤ Θ ≤ 2 ⌈ r
2
⌉
3r ≥ 2r + r
k
Odd Wheel W2k+1 2 1 4 ≥ 2 + 2k
cloned 5∗ 2 7∗ ≥ 4 + 4
k
r-Inflated
⌈
5r−1
2
⌉∗ ⌈ 5r−1
6
⌉∗ ≤ Θ ≤ 2 ⌈ r
2
⌉
3r + 1∗ ≥ 2r + 2r
k
Gen. Series Parallel 2 1 ≤ 3
cloned ≤ 5∗ 2 ≤ 6
r-Inflated ≤
⌈
5r−1
2
⌉∗ ≤ 2 ⌈ r
2
⌉
≤ 3r
Circulant C2n(1, 2) 3 1 ≤ 4 2nb 2n
3
c
cloned 5∗ 2 ≤ 8 4nb 2n
3
c
r-Inflated
⌈
5r−1
2
⌉∗ ⌈ 5r−1
6
⌉∗ ≤ Θ ≤ r ≤ 4r 2nrb 2n
3
c
Table 1: Summary.
22 Ars Math. Contemp. 4 (2011) 5–24
8 Open questions
1. The Petersen graph P has thickness two and arboricity two, and hence P [2] has
thickness two. Similarly, the degree three circulants satisfying a1 = n2 but for which
the 2-adic valuation condition is not satisfied in Theorem 6.7 are thickness two and so
are their clones. Characterize those thickness two graphs H for which the thickness
of H[2] is precisely two.
2. More generally, if G has thickness r, what can be said of Θ(G[r]) for any r ≥ 2?
3. Are cloned planar graphs that have thickness two always permuted layer graphs? In
particular, is it always the case that a cloned planar graph can be decomposed into
two layers, one of which is isomorphic to a subgraph of the other?
4. The technique used in Section 6.5 can be slightly modified to give an upper bound on
the thickness of the r-inflation of any unicyclic graph G. That is, removing any edge
from the cycle in G leaves a forest. The r-inflation of a forest has thickness at most⌈
r
2e . The removed edge, once r-inflated, induces aKr,r, which has thickness
⌊
r+5
4 c .
Thus Θ(G) is bounded above by
⌈
r
2e +
⌊
r+5
4 c . Can this method or a modification
be applied to more general classes of graphs?
5. Jackson and Ringel wrote about variations on Ringel’s Earth-Moon problem in [30].
In the spirit of their article, given a graph G, instead of asking for a t-layer decom-
position of G on t spheres, allow any set of t surfaces, both orientable and nonori-
entable. What can be reasonably asked and answered in this setting?
9 Acknowledgement
The authors wish to thank an anonymous referee for comments that inspired a better upper
bound for Θ(Cn[r]) in Section 6.5.
References
[1] A. Adam, Research problem 2-10, J. Combin. Theory 2 (1967), 393.
[2] M. O. Albertson, D. L. Boutin and E. Gethner, The thickness and chromatic number of r-
inflated graphs, Discrete Math. 310 (2010), 2725–2734.
[3] V. B. Alekseev and V. S. Gončakov, The thickness of an arbitrary complete graph, Mat. Sb.
(N.S.) 101(143) (1976), 212–230.
[4] B. Alspach and T. D. Parsons, Isomorphism of circulant graphs and digraphs, Discrete Math.
25 (1979), 97–108.
[5] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976),
711–712.
[6] K. Appel and W. Haken, A proof of the four color theorem, Discrete Math. 16 (1976), 179–180.
[7] K. Appel and W. Haken, Supplement to: “Every planar map is four colorable. I. Discharg-
ing” (Illinois J. Math. 21 (1977), 429–490) by Appel and Haken; “II. Reducibility” (ibid. 21
(1977), 491–567) by Appel, Haken and J. Koch. Illinois J. Math. 21 (1977), 1–251 (microfiche
supplement).
[8] K. Appel, W. Haken and J. Koch, Every planar map is four colorable. Part II. Reducibility,
Illinois J. Math., 21 (1977), 491–567.
M. O. Albertson et al.: More results on r-inflated graphs. . . 23
[9] L. W. Beineke, Complete bipartite graphs: Decomposition into planar subgraphs, in A Seminar
on Graph Theory, pages 42–53, Holt, Rinehart and Winston, New York, 1967.
[10] L. W. Beineke, F. Harary and J. W. Moon, On the thickness of the complete bipartite graph,
Proc. Cambridge Philos. Soc. 60 (1964), 1–5.
[11] D. L. Boutin, E. Gethner and T. Sulanke, Thickness-two graphs Part I: New nine-critical graphs,
permuted layer graphs, and Catlin’s graphs, J. Graph Theory 57 (2008), 198–214.
[12] Paul A. Catlin, Hajós’ graph-coloring conjecture: variations and counterexamples, J. Combin.
Theory Ser. B 26 (1979), 268–274.
[13] P. A. Catlin, J. W. Grossman and A. M. Hobbs, Graphs with uniform density, Congr. Numer.
65 (1988), 281–285.
[14] R. Diestel, Graph Theory, Volume 173 of Graduate Texts in Mathematics, Springer-Verlag,
New York, second edition, 2000.
[15] R. J. Duffin, Topology of series-parallel networks, J. Math. Anal. Appl. 10 (1965), 303–318.
[16] V. Dujmović and D. R. Wood, Graph treewidth and geometric thickness parameters, in Graph
Drawing, volume 3843 of Lecture Notes in Comput. Sci., pages 129–140, Springer, Berlin,
2006.
[17] V. Dujmović and D. R. Wood, Graph treewidth and geometric thickness parameters, Discrete
Comput. Geom. 37 (2007), 641–670.
[18] B. Elspas and J. Turner, Graphs with circulant adjacency matrices, J. Combinatorial Theory 9
(1970), 297–307.
[19] G. Gao and X. Zhu, Star-extremal graphs and the lexicographic product, Discrete Math. 152
(1996), 147–156.
[20] M. Gardner, Mathematical games, Scientific American, 242 (1980), 14–19.
[21] M. Gardner, The Last Recreations, Copernicus, New York, 1997.
[22] M. R. Garey and D. S. Johnson, Computers and Intractability; A Guide to the Theory of NP-
Completeness, W. H. Freeman & Co., New York, NY, USA, 1990.
[23] M. R. Garey, D. S. Johnson and L. Stockmeyer, Some simplified NP-complete problems, in
STOC ’74: Proceedings of the sixth annual ACM Symposium on Theory of Computing, pages
47–63, New York, NY, USA, ACM Press, 1974.
[24] E. Gethner and T. Sulanke. Thickness-two graphs part two: More new nine-critical graphs,
independence ratio, cloned planar graphs, and singly and doubly outerplanar graphs, Graph.
Comb. 25 (2009), 197–217.
[25] P. J. Heawood, Map-colour theorem, Quart. J. Pure Appl. Math., 24 (1980), 332–338.
[26] C. Heuberger, On planarity and colorability of circulant graphs, Discrete Math. 268 (2003),
153–169.
[27] A. M. Hobbs, H.-J. Lai, G. Weng and H. Lai, Uniformly dense generalized prisms over graphs,
in Proceedings of the Twenty-third Southeastern International Conference on Combinatorics,
Graph Theory, and Computing (Boca Raton, FL, 1992), volume 91, pages 99–105, 1992.
[28] J. P. Hutchinson. Coloring ordinary maps, maps of empires and maps of the moon, Mathematics
Magazine 66 (1993), 211–226.
[29] B. Jackson and G. Ringel, Maps of m-pires on the projective plane, Discrete Math. 46 (1983),
15–20.
[30] B. Jackson and G. Ringel, Variations on Ringel’s earth-moon problem, Discrete Math. 211
(2000), 233–242.
24 Ars Math. Contemp. 4 (2011) 5–24
[31] T. R. Jensen and B. Toft, Graph Coloring Problems, Wiley-Interscience Series in Discrete
Mathematics and Optimization, John Wiley & Sons Inc., New York, 1995.
[32] P. C. Kainen, Some recent results in topological graph theory, in Graphs and Combinatorics
(Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973), pages 76–108, Lec-
ture Notes in Math., Vol. 406. Springer, Berlin, 1974.
[33] A. B. Kempe, On the Geographical Problem of the Four Colours, Amer. J. Math. 2 (1879),
193–200.
[34] N. M. Korneyenko, Combinatorial algorithms on a class of graphs, Discrete Appl. Math., 54
(1994), 215–217.
[35] A. Mansfield, Determining the thickness of graphs is NP-hard, Math. Proc. Cambridge Philos.
Soc. 93 (1983), 9–23.
[36] C. St. J. A. Nash-Williams, Decomposition of finite graphs into forests, J. London Math. Soc.,
39 (1964), 12.
[37] M. D. Plummer, M. Stiebitz and B. Toft, On a special case of Hadwiger’s conjecture, Discuss.
Math. Graph Theory 23 (2003), 333–363.
[38] G. Ringel, Färbungsprobleme auf Flächen und Graphen, volume 2 of Mathematische Mono-
graphien, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959.
[39] N. Robertson, D. P. Sanders, P. Seymour and R. Thomas, A new proof of the four-colour
theorem, Electron. Res. Announc. Amer. Math. Soc., 2 (1996), 17–25.
[40] E. R. Scheinerman and D. H. Ullman. Fractional Graph Theory, Wiley-Interscience Series in
Discrete Mathematics and Optimization, John Wiley & Sons Inc., New York, 1997.
[41] T. Sulanke, Personal communication, 2005.
[42] C. Thomassen, Some remarks on Hajós’ conjecture, J. Combin. Theory Ser. B 93 (2005),
95–105.
[43] W. T. Tutte, The non-biplanar character of the complete 9-graph, Canad. Math. Bull., 6 (1963),
319–330.
[44] R. Wilson, Four Colors Suffice. How the Map Problem was Solved, Princeton University Press,
Princeton, NJ, 2002.