Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 25–27
Graphs with chromatic numbers strictly less
than their colouring numbers∗
Xuding Zhu
Department of Mathematics, Zhejiang Normal University, Zhejiang, P. R. China, and
Department of Applied Mathematics, National Sun Yat-sen University, Taiwan
Received 26 April 2010, accepted 26 August 2010, published online 18 October 2010
Abstract
The colouring number of a graph G, defined as col(G) = 1 + maxH⊆G δ(H), is an
upper bound for its chromatic number. In this note, we prove that it is NP-complete to de-
termine whether an arbitrary graph G has chromatic number strictly less than its colouring
number.
Keywords: Chromatic number, colouring number, Szekeres-Wilf inequality, NP-completeness.
Math. Subj. Class.: 05C15
1 Main result
An easy upper bound for the chromatic number of a graph G is that χ(G) ≤ ∆(G) + 1,
where ∆(G) is the maximum degree of G. This upper bound is sharp; however, Brooks’
Theorem [1] shows that the bound is only attained by complete graphs and odd cycles.
The colouring number col(G) of G is defined as col(G) = 1 + maxH⊆G δ(H), where
δ(H) is the minimum degree of H . The Szekeres-Wilf inequality χ(G) ≤ col(G) gives a
better upper bound for χ(G) [3]. This upper bound is also an easy bound, as the colouring
number of G can be calculated in linear time as follows: Assume G has n vertices. Let
G0 = G, and for 1 ≤ i ≤ n − 1, let Gi = Gi−1 − vi, where vi is a vertex of minimum
degree in Gi−1. Then col(G) = max δ(Gi) + 1. One naturally wonders if there is an
analog of Brooks’ Theorem that gives a simple characterization of all the graphs G for
which the Szekeres-Wilf inequality holds with equality. This note shows that it is unlikely
to have a simple characterization for such graphs, as it is NP-complete to decide whether
χ(G) < col(G) for an arbitrary graph G.
∗In memory of Michael O. Albertson.
E-mail address: zhu@math.nsysu.edu.tw (Xuding Zhu)
Copyright c© 2011 DMFA Slovenije
26 Ars Math. Contemp. 4 (2011) 25–27
Theorem 1.1. The following decision problem is NP-complete:
Instance: A graph G.
Question: Is χ(G) < col(G)?
Proof. As col(G) can be computed in linear time, it is obvious that the problem is in NP.
In the following, we reduce the well-known NP-complete 3-colourability problem to the
above decision problem.
Suppose we need to decide whether a given graph G is 3-colourable. If col(G) ≤ 3,
then χ(G) ≤ col(G) ≤ 3 and G is 3-colourable.
Assume col(G) = k ≥ 4. We construct a new graph G′ as follows: Take a copy of G.
For each 4-subset X of V (G), add a set UX of k − 4 new vertices. Add edges to connect
every pair of vertices in UX (so that UX induces a copy of Kk−4), and connect each vertex
of UX to every vertex of X (the vertices in X are ‘old’ vertices in V (G)). For different
4-subsets X,X ′ of V (G), UX and UX′ are disjoint. Also UX is disjoint from V (G). So if
G has n vertices, then G′ has n +
(
n
4
)
× (k − 4) ≤ n5 vertices. Note that if k = 4, then
G′ = G.
We shall show that G is 3-colourable if and only if χ(G′) < col(G′). Since all the new
vertices (i.e., vertices not in V (G)) have degree k−1, we know that col(G′) = col(G) = k.
If k = 4, then G = G′ and χ(G′) < col(G′) = 4 is equivalent to G = G′ is 3-colourable.
Assume k ≥ 5. If G has a 3-colouring f , then we can extend f to a (k − 1)-colouring
of G′. This is so, because if v is an added vertex, then v ∈ UX for some 4-subset X of
V (G). The vertex v has k− 1 neighbours, and at least two of the neighbours of v in X are
coloured by the same colour. So we can choose a colour for v which is not used by any of
its neighbours.
Conversely, assuming G is not 3-colourable, we shall show that G′ is not (k − 1)-
colourable. Assume to the contrary that f is a (k − 1)-colouring of G′. Since G is not
3-colourable, the restriction of f to V (G) uses at least 4 colours. So there is a 4-subset X
of V (G) such that |f(X)| = 4. As each vertex of X is adjacent to all the vertices in UX ,
none of the 4 colours in f(X) can be used by any vertex in UX . So the number of colours
that can be used on the vertices of UX is |UX | − 1. This is impossible, as UX induces a
complete graph.
So the problem of deciding whether G is 3-colourable is reduced to the problem of
deciding whether χ(G′) = col(G′). As |V (G′)| ≤ |V (G)|5, the reduction is polynomial.
So it is NP-complete to decide whether an arbitrary graph G′ satisfies the strict inequality
χ(G′) < col(G′).
Acknowledgement
The author thanks Professor Wilf for asking this question during the coffee break at the
conference “CoNE Revisited: Celebrating the Inspirations of Michael O. Albertson”.
References
[1] R. L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philos. Soc. 37 (1947),
194–197.
[2] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-
Completeness, W. H. Freeman, New York, 1979.
X. Zhu: Graphs with chromatic numbers strictly less than their colouring numbers 27
[3] G. Szekeres and H. S. Wilf, An inequality for the chromatic number of a graph, J. Comb. Theory
4 (1968), 1–3.