Informática 17 (1993) 59-63
59
REGULAR GRAPHS ARE 'DIFFICULT' FOR COLOURING
Janez Zerovnik
University of Maribor, Faculty of Technical Sciences,
Smetanova 17, Maribor,
Slovenia
Keywords: graph colouring, decision problem, NP-completeness, regular graphs Edited by: Rudi Murn
Received: December 19, 1992 Revised: February 16, 1993 Accepted: March 1, 1993
Abstract: Let k be 3 or 4. In this two cases we prove thai the decision problem of k-colourability when restricted to A-regu/ar graphs is NP-complete for any A > k + 1.
1 Introduction
In this note we consider the time complexity of the decision problem of (vertex) fc-colourability restricted to regular graphs.
It is known that 'almost all ¿-colourable graphs are easy to colour', namely the proportion of 'difficult' graphs for the usual backtrack algorithm vanishes with growing problem size [9]. Knowing this it is not surprising that there are algorithms with average polynomial time complexity [1], when average is taken over all graphs and even when the average is taken over all 3-colourable graphs with a given number of vertices[5].
If P^NP, then for every algorithm there has to be a class of 'counterexamples', i.e. graphs on which the algorithm either has superpolynomial time complexity or it fails to produce a correct answer.
For example, Petford and Welsh noticed that one of the situations in which the 3-colourable graphs were not efficiently coloured by their randomised algorithm is when graphs are approximately regular of a low vertex degree [8]. Similarly, approximately regular graphs of a relative low vertex degree are 'difficult' also for the ¿-colouring generalisation of their algorithm [10]. Petford and Welsh conjectured that 'dense1 graphs are easy. Indeed, Edwards showed that, when restricted to class of graphs with lowest vertex degree 8 > em for arbitrary a > 0, the decision problem of 3-colouring is polynomial [4],
This may be understood that the 'difficult' graphs are likely to be found among 'sparse' graphs. It is known that the problem of 3-
colouring is NP-complete (even) when restricted to graphs of maximal vertex degree 4 [6]. Here we show that the problem can be further 'simplified', proving that the decision problem of 3-colouring is NP-complete when restricted to A-regular graphs (for A > 4). We also show that the decision problem of 4-colouring is NP-complete when restricted to A-regular graphs (for A > 5).
We assume that the reader is familiar with some standard definitions of graph theory and of computational complexity theory (given, for example, in [2] and [7]).
2 3-colourability of 4-regular graphs is NP-complete
Let us define the problem II(fc, A) as follows: Input: A-regular graph G Question: Is G k-colourable?
Lemma 1 For any graph G there is a graph G' with no vertex of degree 1 or 2 such that: G is 3-colourable iff G' is 3-colourable
Remark: G' in the Lemma is either a graph with minimal vertex degree > 3 or the empty graph, which is the case when G is, for example, a cycle. If G' is empty, it is trivially 3-colourable, and from the proof of the Lemma 1 it follows that also G is 3-colourable.
Proof (of Lemma 1): It is easy to see that the following assertions are true:
(a) If there is a vertex t? € V{G) with degree 1, then G is 3-colourable if and only if the
60
Informatica 17 (1993) 59-63
J. Zerovnik
(a)

Figure 1: Vertices of degree 1 or 2 may be omitted
The construction, given in Fig. 2, can be done as follows. Take two sets, say M and N, of three vertices each. Connect every pair x,y; x € M and y € N. Add two vertices, say u and v and connect u to all the vertices of N and v to all the vertices of M. Now choose arbitrary pair of distinct vertices of G, say w and z, and connect u with w and v with z to get the graph G'. Proof: Since the graph H is bipartite, it is easy to see that 3-colouring of arbitrary graph (G on Fig. 2) can be extended to 3-colouring of graph G'. On the other hand, since G is subgraph of G', G is 3-colourable if G' is.	Q.E.D.
Now we shall prove
Figure 2: G is 3-colourable iff G' is 3-colourable
induced graph on V \ {u} is 3-colourable (see Fig. 1(a)).
(b) If there is a vertex v € V^(<?) with degree 2, then G is 3-colourable if and only if the induced graph on V \ {u} is 3-colourable (see Fig. 1(b)).
In this way we can reduce any graph G to a graph G' with minimal vertex degree at least 3 which is 3-colourable exactly when G is. Q.E.D.
Remark: Extracting G' successively using (a) and (b) can clearly be done efficiently. Remark: It is obvious that maximal vertex degree of the graph 6" is not greater than maximal vertex degree of the original graph G.
Lemma 2 G is 3-colourable iff G' is 3-colourable
where G' is a graph, obtained from G by the construction given in Fig. 2.
Lemma 3 The problem 11(3,4) is NP-complete.
Proof: We will reduce the problem of 3-colourability of graphs with vertex degree at most 4 (which is known to be NP-complete [6]) to the problem 11(3,4).
Let G be arbitrary graph with maximal degree A < 4. By Lemma 1 there is a graph G\ (which has at most as many vertices as G) and (?i is 3-colourable exactly when G is 3-colourable. If G\ is empty, then we know that G is 3-colourable.
Now consider the case when G\ is nonempty. By construction, G\ is a graph with vertex degrees 3 and 4. Since the sum of all the vertex degrees is twice the number of edges (£„ev = 2|J5|), the number of vertices with degree 3 must be even.
Now couple vertices of degree 3 in G\ arbitrarily. Connect a copy of the graph H to each couple of vertices of degree 3, as defined in Fig. 2. By Lemma 2, this construction gives a graph (?2 which is 3-colourable exactly when G\ is 3-colourable.	Q.E.D.
Remark: Graph H has 8 vertices. Since we added at most new vertices, the resulting graph C?2 has at most a constant factor more vertices than G\.
Remark: The construction can clearly be done efficiently.
Thus 3-colourability of 4-regular graphs is NP-complete. Now we reduce the problem of 3-colourability of A-regular graphs to the same problem on A + 1-regular graphs.
REGULAR GRAPHS ARE 'DIFFICULT' FOR COLOURING
Informática 17 (1903) 59-63
61
g(u)g(v)9(G) J

m
J
v)
Figure 3: Joining two copies of a A-regular graph we get a A + 1-regular graph
3 3-colourability of A-regular graphs is NP-complete
Lemma 4 11(3, A) oc n(3, A + 1)
Proof: Let G be arbitrary A-regular graph. Now we give a construction of a graph G'.
Take two copies of G, G\ — (Vj, and <?2 = ('V2, E2). Denote with / : G <?i and g : G G% the corresponding isomorphisms.
Graph G' = (V', E') is defined with: V' = V1 U V2 and E' = f^U^U {{/(»),*(*)} | t> € V} (see Fig. 3).
If G' is 3-colourable, then also G is 3-colourable, since it is isomorphic to a subgraph in G'.
On the other hand, if we have a 3-colouring 6 of <j, it is easy to construct a 3-colouring b' of G', for example with a 'shift' of colours: b'(f{v)) - b(v) and	= (6(v) mod 3) + 1.
Since for any A size blow up is a constant factor, the assertion of the Lemma follows. Q.E.D.
By induction, from Lemma 3 and Lemma 4 we have:
4 4-colourability of Regular Graphs
Here we discuss an attempt to generalise the proposition 1 on the problem of k-colouring. With analogous proof as for the case of 3-colourings we prove a proposition for 4-colouring, while for k > 4 the time complexity of the decision problem of k-colouring of A-regular graphs remains open for some A.
Two of the previous lemmas are easily generalised:
Lemma 5 Let G' be any subgraph of G obtained by the following process: if there is a vertex of degree less than k, delete it. Graph G is k-colourable if and only if graph G' is k-colourable.
Proof: Assume we coloured the graph G' with fc-colours. It is easy to see that there is algorithm, which properly extends the proper colouring of G' to a proper colouring of G. (Take, for example, vertices of G in opposite order as they were deleted from G. When a vertex was deleted, it had less than k neighbours, therefore there is at least one free colour for it.)	Q.E.D.
Lemma 6 For any graph G with vertex degrees k andk + 1 there is a k +1-regular graph G', such that:
G is k-colourable iff G' is k-colourable
H
Proposition 1 The decision problem of 3-colouring restricted to A-regular graphs 11(3, A) is NP-complete for A > 4.
It is known that for graphs of maximal vertex degree 3 the problem is polynomial [6]. Hence we know for all problems 11(3, A) whether they are polynomial or NP-complete.
Figure 4: G is 4-colourable iff G' is 4-colourable
Proof: If there are at least two vertices of degree k in G, then we add a copy of graph H. For given k the graph H is defined as follows. Take a complete bipartite graph Kk,k- Add two vertices
62 Informática 17 (1993) 59-63
J. Zerovnik
and connect one vertex with all the vertices of one independent set of the Kk,k and the other vertex with the second independent set of the K^k (for the case k = 4 see Fig. 4). In this way we reduce the number of vertices of degree k by two.
If there is only one vertex of degree k in G, then we construct a new graph as follows: Take two copies of G, connect the two vertices of degree k with an edge. The resulting graph is obviously fc + 1-regular and it is easy to see that it is ¿-colourable exactly when G is fc-colourable. Q.E.D.
For a proof of a generalization of the proposition 1 we need a lemma of the following type: decision problem of /¡¡-colouring on arbitrary graph can be reduced to the same problem on a graph of maximal vertex degree k + 1.
In the proof of the proposition for 3-colouring we used the result of Garey, Johnson and Stockmayer. Here we give the idea of a proof for k = 4. We were not able to generalise the idea for A >4.
Lemma 7 The decision problem of 4-colouring of graphs of vertex degree < 5 is NP-complete.
Figure 5: Graph for substituting vertices of degree 6
Proof (outline): The key of the proof is the idea of how to substitute vertices of large degree with a graph of small enough maximal vertex degree and with property that any 4-colouring of the resulting graph Gt defines a 4-colouring of the original graph G. Such graphs are given in Figures 5,6 and 7. The graphs in Fig, 5 and Fig. 6 are used for substituting vertices of degrees 6 and 7, respectively. For vertices of larger degrees, a longer chain is used, as indicated on Fig. 7. The graphs given have the property, that in any proper 4-colouring all the vertices with 'free edges' have to be coloured with the same colour. (This colour
Figure 6: Graph for substituting vertices of degree 7
can be then assigned to the substituted vertex in the original graph. The other vertices of G can then be assigned the same colours as they had in the 4-colouring of Gt.) We omit the details. Q.E.D.
With a straightforward generalization of the proof of Lemma 4 we have also:
Lemma 8 Jl(k, A) oc II(fc, A + 1)
Therefore:
Proposition 2 The decision problem of 4-colouring of A-regular graphs 11(4, A) ¡5 NP-complete for any A > 5.
Again, because of the theorem of Brooks [3], the problem 11(4, A) has polynomial time complexity for A < 4. Thus for all the problems 11(4, A) we know whether they are polynomial or NP-complete. Let us conclude with a couple of conjectures. Since we were unable to generalise the Lemma 7 we state
Conjecture 1 The decision problem of k-colouring of graphs with vertex degree < k + 1 is NP-complete.
If the first conjecture was true, then we would have a nice classification of time complexity for all the problems !!(/;, A).
Conjecture 2 For any k > 2, A > 2 the decision problem of k-colourability of A-regular graphs II(fc, A) is NP-complete if A > k and is polynomial otherwise.
Let us conclude with a simple consequence of the proposition. Assume we have an algorithm
REGULAR GRAPHS ARE 'DIFFICULT' FOR COLOURING
Informatics 17 (1993) 59-63 63
Figure 7: Graph for substituting vertices of degree > 5
A for 3-colouring and we want to characterise graphs, for which the algorithm does not provide the correct solution in polynomial time. If P^NP then for any algorithm A for each A > 4 there exists an infinite family F(A, A) of A-regular graphs such that the algorithm A has superpoly-nomial complexity on each family F(A, A). If this were not the case for some A then A would be a polynomial algorithm for 3-colouring of A-regular graphs, which would imply P=NP!
Acknowledgement. The contents of the paper is based on a part of author's dissertation submitted to University of Ljubljana under supervision of Tomaž Pisanski. Thanks are also due to the anonymous referees, who helped to improve the quality of presentation considerably.
References
[1]	E.A. Bender, H.S. Wilf, A Theoretical Analysis of Backtracking in the Graph Coloring Problem, Journal of Algorithms 6 (1985) 175-282.
[2]	J .A. Bondy, U.S.R. Murty, Graph Theory with Applications, Amer. Elsevier, New York, 1976.
[3]	R.L. Brooks, On Coloring the Nodes of a Network, Proc. Camb. Phil. Soc 37 (1941) 194-197.
[4]	K. Edwards, The Complexity of Colouring Problems on Dense Graphs, T/ieoreifca/ Computer Science 43(1986) 123-147.
[5]	J.A. Ellis, P.M. Lepolesa, A Las Vegas Graph Colouring Algorithm, The Computer Journal 32 (1989) 474-476.
[6]	M.R,. Garey, D.S. Johnson, L. Stockmeyer, Some Simplified NP-complete Graph Problems, Theoretical Computer Science 1 (1976) 237-267.
[7]	M.R. Garey, D.S. Johnson, Computers and Intractability, W.H. Freeman and Co., San Francisco, 1979.
[8]	A.D. Petford, D.J .A. Welsh, A Randomised 3-Colouring Algorithm, Discrete Math., 74 (1989) 253-261.
[9]	J.S. Turner, Almost All ¿-Colorable Graphs Are Easy to Color, Journal of Algorithms 9 (1988) 63-82.
[10] J. Zerovnik, A Randomized Algorithm for fc-colorability, Discrete Mathematics (to appear).