Also available at http://amc.imfm.si
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 1–6
Chromatic Number, Independence Ratio, and
Crossing Number
Michael O. Albertson
Department of Mathematics and Statistics
Smith College, Northampton, MA 01063, USA
Received 18 July 2007, accepted 29 November 2007, published online 17 June 2008
Abstract
Given a drawing of a graph G, two crossings are said to be dependent if they are incident
with the same vertex. A set of crossings is independent if no two are dependent. We con-
jecture that if G is a graph that has a drawing all of whose crossings are independent, then
the chromatic number of G is at most 5. We show that this conjecture is true if the crossing
number of G is at most three. We also show that if all crossings are independent, then the
chromatic number of G is at most 6, and the independence ratio of G is at least 316 .
Keywords: Graphs, chromatic number, crossing number.
Math. Subj. Class.: 05C15, 05C10
1 Introduction
Progress towards the Four Color Theorem has had an enormous and continuing impact on the
development of graph theory. One consequence is that it is compelling to consider whether
a particular relaxation of planarity forces an upper bound on the chromatic number. We
revisit the three classic generalizations of planarity. For more than a century there has been a
coloring theorem for graphs embedded on surfaces of positive Euler genus. For almost forty
years we have known that that coloring theorem is best possible. Restricting our attention
to graphs of a given thickness, we know a relatively small interval in which the maximum
chromatic number must live, though narrowing that interval appears difficult. Surprisingly,
there are almost no results on coloring graphs with a given crossing number. The purpose of
this paper is to provoke further work on the relationship between the crossing number and
the chromatic number or especially the independence ratio. Towards this end we introduce
a refinement to the idea of crossing and use this refinement to give bounds on these two
E-mail address: albertson@math.smith.edu (Michael O. Albertson)
Copyright c© 2008 DMFA – založništvo
2 Ars Mathematica Contemporanea 1 (2008) 1–6
parameters for certain families of graphs. Section 2 provides the necessary background,
mentions what has been done before, and develops some bounds. Section 3 gives results and
proofs. We offer two explicit and many implicit open questions.
2 Background
Suppose G is a graph with n vertices and chromatic number χ(G). Recall that U ⊆ V (G)
is said to be independent if x, v ∈ U ⇒ xv /∈ E(G). The independence number of G,
denoted by α(G), is the cardinality of a maximum independent set in G. The independence
ratio, denoted by µ(G), is defined by µ(G) = α(G)n . Since
n
χ(G) is the average size of
a color class in a χ(G)-coloring of G, α(G) ≥ nχ(G) and µ(G) ≥
1
χ(G) . Results on the
independence ratio of locally planar graphs (those embedded on a given surface with large
(edge) width [2]) preceded and, in one sense, are stronger than the results about chromatic
numbers for this same class of graphs. It is well known that locally planar graphs on a
given surface are 5-colorable [4, 6, 12]. The stronger result for independence ratios is given
 > 0, ∃ N(, S) such that if G is a graph with n vertices embedded on S and n ≥ N(, S),
then µ(G) > 14 −  [1, 3]. The earlier of the two papers just cited introduced the name
independence ratio, although the idea had occurred prior to that e.g. in the work of Vizing
and Plesnevič [13].
The crossing number of G, denoted by c = cr(G), is the minimum number of crossings
in any nice drawing of G in the plane. See [11] for a clear explanation of the foundational
issues involved with crossings including the idea of a nice drawing. That paper also presents
a survey of crossing numbers. A bibliography on crossing numbers is maintained in [14].
We will assume that our drawings are both nice and optimal with respect to the number of
crossings.
Naturally, the first question to ask is whether the chromatic number is bounded from
above by a function of the crossing number. To answer this question it is convenient to
examine the incidence relation between vertices and crossings. Suppose e = uv and f = xy
are two edges that cross in a given drawing of G. We say that {u, v, x, y} is the cluster of
vertices associated with the crossing {ef}, and the vertices of the cluster and the crossing
are said to be incident with each other. The crossing covering number of a graph G, denoted
by ρ(G), is the minimum over all (both optimal and nice) drawings of G of the minimum
cardinality of a set of vertices subject to the condition that every crossing is incident with at
least one vertex in the set.
Theorem 1. χ(G) ≤ 4 + ρ(G).
Proof. Given the drawing of G, let C denote the set of vertices in a minimum crossing cover.
Let G0 denote the subgraph of G induced by the vertices that are not in C. Since G0 is
planar, the vertices of G0 can be colored using colors 1, 2, 3, 4. The vertices in C can each be
assigned a unique color using colors 5, 6, . . . , 4 + ρ(G).
Noting that ρ(G) ≤ cr(G) = c we immediately get.
Corollary 2. χ(G) ≤ 4 + c.
Theorem 1 is best possible in the sense that for any integer r ≥ 0, there exists a (4 + r)-
chromatic graph which has ρ(G) = r. To accomplish this join every pair of vertices in C.
This will create an r-clique; however, C is still a minimum crossing cover of the resulting
M. O. Albertson: Chromatic Number, Independence Ratio, and Crossing Number 3
graph. Then one needs to assure that G0 is 4-chromatic and that every vertex in C is adjacent
to every vertex in G0. Corollary 2 is best possible if cr(G) ≤ 1 but not so much for larger
values of the crossing number. Since cr(Kn) = Θ(n4), one might expect the right bound in
Corollary 2 to be O(c1/4).
In the context of crossings and colorings the second natural question to ask would be what
hypotheses on the crossings force the chromatic number to be relatively small. There have
been a few minor results detailed below, and we will offer some more in the next section.
However, the independence ratio may be a better measure of the near planarity of a given
graph G than its chromatic number. A drawing of a graph with a given number of crossings
may have these crossings concentrated in a relatively small subgraph that has a relatively
large chromatic number. Alternatively, it may have the crossings dispersed throughout the
drawing and have relatively small chromatic number. In either case one expects that the
independence ratio will be relatively large. We formalize this observation in the theorem
below but emphasize that its interest is limited to instances where the number of vertices is
much larger than the crossing number.
Theorem 3. Suppose G has a drawing of a graph with n vertices and c crossings. For any
 > 0, if n ≥ c4 , then µ(G) ≥
1
4 −  .
Proof. LetG0 be the graph obtained by removing one vertex from each cluster of the drawing
of G. Evidently, G0 is planar, α(G) ≥ α(G0) ≥ n−c4 , and the result follows.
We return to colorings. It is straightforward to show that if cr(G) = 1, then χ(G) ≤ 5.
One way to see this is to apply Theorem 1. Oporowski and Zhao proved the two results below
and asked the open question that follows.
Theorem 4 ([7]). If cr(G) ≤ 2, then χ(G) ≤ 5.
Since cr(K6) = 3 one cannot extend Theorem 4 without additional hypotheses. Let ω(G)
denote the clique number, the cardinality of a largest clique contained in G.
Theorem 5 ([7]). If cr(G) = 3 and ω(G) ≤ 5, then χ(G) ≤ 5.
Let K3 ∨ C5 denote the join of triangle and a 5-cycle. Note that cr(K3 ∨ C5) = 6, χ(K3 ∨
C5) = 6, and ω(K3 ∨ C5) = 5. This inspires the following.
Question 6 ([7]). If cr(G) ≤ 5 and ω(G) ≤ 5, is χ(G) ≤ 5?
We close this section by introducing a refinement to the notion of crossing that will force a
coloring theorem.
Definition 7. In a drawing of a graph, two crossings are said to be dependent if their clusters
have a common vertex. A set of crossings is said to be independent if no two are dependent.
3 Graphs with Independent Crossings
Theorem 8. If G is a graph which has a drawing in the plane in which there are at most
three crossings, no two of which are dependent, then χ(G) ≤ 5 and µ(G) ≥ 15 .
4 Ars Mathematica Contemporanea 1 (2008) 1–6
ua
u
u
u
bu
v
u
w
uc
u
x
ud
e
e
e
e
e
e%
%
%
%
%
%
%
%
%
%
%
%e
e
e
e
e
e e
e
e
e
e
e %
%
%
%
%
%
{(av, bu)(vc, bw)} dependent
{(av, bu)(cx, dw)} not dependent
Figure 1: Dependent and Independent Clusters
vui
v
yi
v
xiv
vi
Q
Q
Q
Q
Q
Q
Q
Q
Q
Q









Figure 2: Clusters Induce K4’s
Proof. By Theorem 4 we may assume that there are exactly three crossings. For 1 ≤ i ≤ 3,
let Ci = {ui, vi, xi, yi} denote the cluster of vertices associated with the ith crossing. By the
independence of the crossings these vertices are all distinct. We assume that the vertices are
labeled so that uivi crosses xiyi. We may assume that each Ci induces a K4. If it does not,
we can add edges to the cluster without creating any additional crossings by joining e.g. ui
to xi, with an edge that is drawn within a small neighborhood of the crossing pair of edges.
This is illustrated with the dotted edge in the figure below.
Consider G0 = G[∪3j=1Cj ], the subgraph of G induced by the clusters C1, C2, and C3.
|V (G0)| = 12. Since G0 has three independent crossings, Euler’s formula implies that
|E(G0)| ≤ 33. Since we are assuming each cluster contains 6 edges, there are at most 15
edges joining vertices in one cluster with vertices in another.
Claim 9. ∃ Z = {z1, z2, z3 : zi ∈ Ci and Z is an independent set}.
Proof of claim. Since there are four choices for each zi, there exist 64 candidates for Z. If
the claim fails for a particular candidate set, there must be at least one edge joining two of
the three vertices of Z. Each edge joining two vertices in different clusters is contained in
4 candidate sets. Thus, if the claim fails there must be at least 16 edges joining vertices in
different clusters. Since there are at most 15 such edges, the claim holds.
Continuing the proof of Theorem 8, given the independent set Z = {z1, z2, z3} for 1 ≤
i ≤ 3 let ei denote the crossing edge in Ci that is incident with zi. Set G1 = G− {∪3i=1ei}.
Since G1 is planar, we 4-color G1 using colors {1, 2, 3, 4}. We then transfer this coloring to
G and recolor each zi with the color 5.
M. O. Albertson: Chromatic Number, Independence Ratio, and Crossing Number 5
A probabilistic argument for the claim in the above theorem was also given by Michael
Sindelair [9].
Although the proof above does not generalize to more than three crossings, the following
conjecture is appealing.
Conjecture 10. If G is a graph which has a drawing in the plane in which no two crossings
are dependent, then χ(G) ≤ 5 and µ(G) ≥ 15 .
Both Stephens [10] and the author noted that there is a straightforward argument that
shows that graphs all of whose crossings are independent are 8-colorable. The following
slightly stronger result generalizes.
Theorem 11. If G is a graph which has a drawing in the plane in which no two crossings
are dependent, then χ(G) ≤ 7 and µ(G) ≥ 17 .
Proof. If G1 is an induced subgraph of G with n1 vertices, then in the restriction of the
drawing of G to the subgraph G1, the number of crossings is at most n14 . Thus there are at
most n14 edges whose removal will make a subgraph of G1 planar. Consequently, |E(G1)| ≤
3n1 − 6 + n14 , and the average degree in G1 is less than 7. The standard greedy coloring of
G will use no more than seven colors.
A straightforward extension of the preceding argument yields the following result.
Theorem 12. If G is a graph which has a drawing in the plane in which every vertex is
incident with at most r crossings, then χ(G) ≤ 6 + d r2e.
Now we get one step closer to the conjecture.
Theorem 13. If G is a graph which has a drawing in the plane in which no two crossings
are dependent, then χ(G) ≤ 6 and µ(G) ≥ 16 .
Proof. Suppose there are r crossings whose vertices form clusters C1, . . . Cr with Ci =
{xi, yi, ui, vi} such that xiyi and uivi cross. Let G1 = G − {∪rj=1xjyj}. Since we have
removed a crossing edge from each induced cluster, G1 is planar. Let γ1 be a 4-coloring of
G1 using colors from {1, 2, 3, 4}. As in the proof of Theorem 8 we may assume that each Ci
induces a K4 in G. This implies that each Ci induces a K4 − e in G1. Thus γ1 necessarily
assigns at least three different colors to the vertices of Ci. For 1 ≤ i ≤ r we choose zi ∈ Ci
such that γ1(zi) ∈ {1, 2} and wi ∈ Ci such that ziwi is a crossing edge in Ci.
Now define G2 = G− {∪rj=1zjwj}. Since we have removed a crossing edge from each
cluster G2 is planar. Let γ2 be a 4-coloring of G2 using colors from {1, 2, 3, 4}. Let γ be a
coloring of G defined as follows. For x 6= zi, 1 ≤ i ≤ r, set γ(x) = γ2(x). For 1 ≤ i ≤ r,
set γ(zi) = γ1(zi) + 4. It is straightforward to check that γ is a 6-coloring of G.
Note that if an edge in a drawing of G crosses two other edges, then these two crossings
are dependent. Thus the hypothesis of no two dependent crossings implies that G can be
drawn in the plane so that no edge crosses more than one other edge i.e. G is 1-embeddable in
the plane. Consequently, Theorem 13 could be achieved as a corollary of Borodin’s Theorem
[5]; however, Borodin’s result, applying to a larger class of graphs, seems to require a difficult
proof.
Theorem 14. If G is a plane graph which has a drawing in the plane in which no two
crossings are dependent, then µ(G) ≥ 316 .
6 Ars Mathematica Contemporanea 1 (2008) 1–6
Proof. If all crossings are independent, then cr(G) ≤ n4 . By choosing one vertex from each
cluster we obtain U ⊂ V (G) such that |U | ≤ n4 and G1 = G[V − U ] is planar. Using the
Four Color Theorem gives that α(G) ≥ α(G1) ≥ 14 ·
3n
4 =
3n
16 .
Repeating a theme mentioned in the preceding section, the proof of this independence
ratio result is easier than the proof of the coloring result, even though the independence result
is, in one sense, stronger.
Postscript: With respect to the discussion following Corollary 2, Marcus Schaefer has shown
that if c = cr(G), then χ(G) = O(c1/4) [8].
References
[1] Michael O. Albertson and Joan P. Hutchinson, On the independence ratio of a graph, J. Graph
Theory 2 (1978), no. 1, 1–8.
[2] Michael O. Albertson and Joan P. Hutchinson, The independence ratio and genus of a graph,
Trans. Amer. Math. Soc. 226 (1977), 161–173.
[3] Michael O. Albertson and Joan P. Hutchinson, The maximum size of an independent set in a
nonplanar graph, Bull. Amer. Math. Soc. 81 (1975), 554–555.
[4] Michael O. Albertson and Walter R. Stromquist, Locally planar toroidal graphs are 5-colorable,
Proc. Amer. Math. Soc. 84 (1982), no. 3, 449–457.
[5] Oleg Borodin, A new proof of a 6-color theorem, J. Graph Theory 19 (1995), 507–521.
[6] Joan P. Hutchinson, A five-color theorem for graphs on surfaces, Proc. Amer. Math. Soc. 90
(1984), no. 3, 497–504.
[7] Bogdan Oporowski and David Zhao, Coloring graphs with crossings, preprint.
[8] Marcus Schaefer, personal communication.
[9] Michael Sindelair, personal communication.
[10] D. Christopher Stephens, personal communication.
[11] László Székely, A successful concept for measuring non-planarity of graphs: the crossing number,
Discrete Math. 276 (2004), no. 1–3, 331–352.
[12] Carsten Thomassen, Five-coloring maps on surfaces, J. Combinatorial Theory Series B 59 (1993),
89–105.
[13] V. G. Vizing and G. S. Plesnevič, On the problem of the minimal coloring of the vertices of a
graph, in Russian, Sibirsk. Mat. Ž 6 (1965) 234–236.
[14] Imrich Vrt’o, Crossing Numbers of Graphs: A Bibliography,
ftp://ftp.ifi.savba.sk/pub/imrich/crobib.pdf