7   Colourings, and other hard problems
We motivate this lecture with a historical excursion: Besides the "7 bridges of Königsberg" problem, another milestone in the early development of graph theory is the "4 colour problem" which originated in the middle of 19th century, and remained unsolved for more than 100 years!
Briefly, the task is to show that any political map can be coloured with just 4 colours. . . Easy? Not, and (unsuccessful, though) attempts to solve this simple looking question stimulated the development of most of the areas of contemporary graph theory.
BTW, yet another historical excursion discovers the "chess knight" problem, much older than the two previous. Can you traverse the complete chessboard with a knight? And how does this very old question relates to modern graph theory?
Brief outline of this lecture
• Definition of a colouring of a graph. Basic properties.
• Some variants of the colouring problems.
• Hamiltonian cycle, and some other "difficult" problems.
Algorithmic complexity (and NP-compl.) of basic graph problems.
7.1   Proper colourings and the chromatic number
Imagine that a given graph models relations between objects, the neighbouring pairs being somehow similar, and in need of a distinguishing "colouring" which makes all adjacent pairs of different colours. How can this be formulated mathematically?
Definition: A (proper) colouring of a graph G with k colours is any assignment
c:V(G)^{\,2,...,k}..
such that every pair of adjacent vertices gets distinct colours, i.e. c(u) ^ c(v) for all {u,v} e E{G).
Definition 7.1. The chromatic number of a graph G
is the least integer x(G) such that G can be properly coloured with x(G) colours.
• The numbers 1,2,... ,k used to colour the vertices of a graph G are naturally called the (vertex) colours (it is easier than to say white, red, blue, black, etc).
• Notice that the chromatic number and colourings make sense only for loopless graphs! Parallel edges, on the other hand, do not matter at all.
Lemma 7.3. Let G be a simple graph (i.e., no loops) and H C G and arbitrary subgraph of it. Then x(G) < x(H).
We say that the chromatic number of a graph is subgraph-monotone. □
Lemma 7.4. Let G be a simple n-vertex graph. Then x(G) < n, and an equality holds if and only if G ~ Kn is complete.
Example 7.5.   What is the relation of the above graph colouring with "map colourings"?
The map regions (assumed connected in the picture) are represened by the vertices of a graph, and neighbouring pairs of regions (sharing a section of a boundary) define the edges of this graph, as in the picture. The meaning of a proper colouring is now clear.
We can, however, find a better colouring of our map, just looking at the derived graph as follows.
□
Theorem 7.6. A nonempty gr. G has chromatic number 1 if and only if G is edge-less. G has chromatic number at most 2 if and only if G contains no odd cycles. □
Proof: The first claim is trivial, c
Considering the second one, we easily see that an odd cycle needs 3 colours. Conversely we may run a breadth-first search (BFS) through G from any v, and colour the vertices by their distance from v — alternatively giving colours 1, 2,1,2,...
Why this simple colouring works; is proper? Notice that any "failure" (i.e. an edge of G between two vertices that got the same colour) would imply an existence of an odd-length closed walk in G, and that in turn forces an existence of an odd cycle, a contradiction. C
7.2   How to Colour a Graph
Greedy approach to graph colouring
Definition: A graph G is k-degenerated if every subgraph of G contains a vertex of degree at most k.
An example of a fc-degenerated graph is that of maximum degree fc, but there exist more fc-degenerated examples with much higher maximum degree. On the other hand, it is not enough for G just to have some vertex of small degree. □
Theorem 7.7. Every k-degenerated graph can be greedily (and properly) coloured by k + 1 colours, c
Proof: We pick any vertex v\ of degree < k, and we recursively colour the subgraph G — vi with k + 1 colours. Then we notice that the neighbours of v\ carry at most k distinct colours, and so we can properly colour also v\ with the remaining colour.
Very easy and nice, right? But the general situation with colouring algorithms will be much more difficult. Still, one slight strengthening is possible.
Theorem 7.8. Let G be a connected simple graph of maximum degree k > 2. Then x(G) < k with the only exceptions when G is an odd cycle or a complete graph.
Proof (a sketch): For k — 2 this follows from Theorem 7.6. Let now k > 3. In one direction, x(Kk+i) — k+l. So assume that G is not complete, and that all degrees in G are equal k (since the greedy approach of Theorem 7.7 could be applied otherwise).□
• In the first step, we find two non-adjacent vertices u,v with a common neighbour w. If G—{u, v} is not connected, we colour it parts separately by induction.
• So G — {u, v} is connected. The second step argues that the graph H resulting from G — w by identifying u with v into one vertex is (k — l)-degenerated. c
• Hence H can be greedily fc-coloured using Theorem 7.7. After we "split" into original u and v, we get a colouring of G — w having u,v of the same colour. Then w "sees" at most k — 1 distinct colours in its neighbourhood of size k, and a proper colour can be chosen for w.
C
Graphs of high chromatic number
Thinking about graphs which cannot be coloured with few colours, the first ones coming to mind are the cliques. But what else, are these the only structures forcing high chromatic number? □
No, we can even show that there exist triangle-free graphs of arbitrarily high chromatic number! For instance, the construction of Mycielski gives:
Proposition 7.9. The graph H obtained from any graph G by the following sketched construction has the chromatic number x(G) + 1, and H is triangle-free if G was.
□
Even more, one can read the following surprisingly strong result of Erdos:
Theorem 7.10. For any c, r > 0 there exists a graph of chromatic number at least c and not containing a cycle of length less than r.
7.3   Variants of colouring problems, and Hamiltonicity
Definition 7.11. The edge chromatic number of a graph G.
We are looking for an edge colouring ce(E(G)) —>• {1, 2,..., k} such that no two edges sharing a vertex have the same colour.
The least number k for which an edge colouring of G exists is called the edge chromatic number \e(G).
The theorem of Vizing gives a sharp approximation of edge chromatic number.
Theorem 7.12. If G is a simple graph, then A(G) < Xe(G) < A(G) + 1. c
For most of graphs, it actually holds A(G) = Xe(G). Can you easily come with graphs of the other kind?
Still, the edge colourability problem remains very hard, and it is also related to the 4 colour problem.
Definition 7.13. Choosability (the list chromatic number) of a graph G. Given is a graph G with an assignment of "colour lists" L : V(G) —>• (^) (fc-element subsets of colours).  The task is to find a list colouring cch(V(G)) —>• N such no two adjacent vertices receive the same colour, and moreover, cch(v) G L(v) for every vertex v.
The least size k of the colour lists which guarantees an existence of a list colouring of G (against all choices of L) is called the choosability (list chromatic number) ch(G) of the graph G.
Proposition 7.14. For every integer k there exists a bipartite (chromatic number 2) graph of choosability greater than k.
Hamiltonian graphs
Definition: A cycle G in a graph G is called Hamiltonian if G spans all vertices of G. A Hamiltonian path P in G is defined analogously.
A graph G is Hamiltonian if G contains a Hamiltonian cycle, c
Though it may sound strange, the Hamiltonian cycle problem is also related to some attempts to solve the 4 colour problem.
Instead, the following result of Dirac has a very nice short proof.
Theorem 7.15. Every graph on n > 3 vertices and with minimum degree > n/2 is Hamiltonian.
7.4   A/^P-completeness of many graph problems
Recall the definition of the class MV - those decision problems for which there exists a polynomial certificate. The NT-complete problems are those having the highest difficulty within the class MV, i.e. those to which every member of MV can be reduced.
□
As we shall see, most of natural graph problems are ./VP-complete. We start the excursion from the following classical "master" problem:
Problem 7.16. 3-SAT (a spec, version of satisfiability)
The following problem is MV-complete:
Input: Logic formula $ in a conjunctive normal form, such that every clause of $
contains < 3 literals. Output: Is there a valuation of the ^-variables that makes $ true?
For instance, $ = (xi V -12:3 V X4) A (X2 V -12:4) A (-1X1 V X2 V 23).
Problem 7.17. 3-COL (3-Colouring of graphs)
The following problem is MV-complete:
Input: Graph G.
Output: Can the vertices of G be properly coloured using three colours?
Proof (a sketch): We show a polynomial reduction from 3-SAT. □ For a given G we construct a formula $: The basis of the graph is a triangle with vertices denoted by X,T,F. Each variable Xj in $ is assigned a vertex pair adjacent to X. Each clause of $ is assigned a subgraph on 6 vertices (three of them adjacent to T), as in the picture. Then the remaining free "halfedges" are joined together in the way corresponding to the literals in the clauses.
Then one may easily check that G has a 3-colouring iff $ is satisfiable.
Z
Problem 7.18. IS (Independent Set)
The following problem is MV-complete:
Input: Graph G, and an integer k.
Output: Is there an independent subset of size (at least) k in Gl □
Proof: We show a polynomial reduction from 3-COL.
Let if be a graph on n vertices which should be 3-coloured.  We set k
construct a graph G made of three disjoint copies of H as shown :
v  > -Tv
— n, and
H
G
Assume c : V(H) —>• {1,2,3} is a 3-colouring of H. Then one can choose k — n independent vertices in G - for each v e V(H) choosing the c(v)-th copy of v in the graph G. Conversely, if I is an independent subset in G of size k — n, then every triangle Tv, v e V(H) intersects I just in one vertex. That determines the colour for v in H. C
Definition: A vertex cover in a graph G is such a set C C V(G) that every edge of G is incident with a vertex of G, i.e. G — G is independent.
Problem 7.19. VC (Vertex Cover)
The following problem is MV-complete:
Input: Graph G, and an integer k.
Output: Is there a vertex cover of size at most k in Gl □
Proof: We show a polynomial reduction from IS. Notice that the complement G = V(G) \ I of an independent set I is actually a vertex cover. So the reduction works with the same graph G and with k — n — i. C
independent set
vertex cover
Definition: A dominating set in a graph G is such a set D C V(G) that every vertex of G not in D has a neighbour in D.
Problem 7.20. DOM (Dominating set)
The following problem is MV-complete:
Input: Graph G, and an integer k.
Output: Is there a dominating set of size at most k in Gin
Proof (a sketch): Given any graph H, we construct an input graph G for DOM as follows: For every edge e G E(H), a new vertex ve is added, forming a triangle with e.
vertex cover dominating set
Now a vertex cover (cf. Problem 7.19) of the former graph is the same as a dominating set in the latter graph. C
Problem 7.21. HC (Hamiltonian cycle, directed)
The following problem is MV-complete:
Input: Directed graph G.
Output: Can we find a directed cycle in G passing through all vertices?^
Problem 7.22. HAM (Hamiltonian cycle)
The following problem is MV-complete:
Input: Graph G.
Output: Can we find a (undirected) circuit in G passing through all vertices?
It is an easy reduction from the previous problem HC. Each vertex v of a directed graph H is replaced with three vertices forming a path Pv in the graph G. then the directed edges coming into v are joined to the first vertex of Pv, and the edges leaving from v
Proof
are joined to the last vertex of Pt
□
7.5   The interesting story of Vertex Cover
Consider the (at first glance) very similar problems of a vertex cover and of a dominating set in a graph—both are among the classical ./VP-complete problems. Yet, we discover a huge difference between them, briefly outlined as follows, c
• If, in the computational complexity analysis, we focus on the value of the input parameter k, then we still cannot solve Dominating Set in a better way than exhaustively checking (almost) all fc-tuples of vertices.
Even when k is fixed small, say k — 10, 20, this an intractable problem, c
• On the other hand, a Vertex Cover of size k can be decided by a very simple algorithm running in time 0(2k ■ n), which is quite usable for small fixed values of k such as k — 10, 20, giving actually a linear time algorithm!
Algorithm 7.24. k-VC (Vertex Cover)
For any fixed k we are solving the following problem.
Input: Graph G.
Output: Is there a vertex cover of size at most k in Gl □ We initialize C — % and F — E(G).
• If F — %, then C is returned as a vertex cover.
If, otherwise, \C\ > k, then the return value is "NO".
• We pick an arbitrary edge f — uv e F, and for each of its ends x — u, v we do:
— C' — C U {x}, and the edge set F' results from F by removing all edges incident with x in G.
— This algorithm is called recursively for G, C' and F'. c
Finally, how many (self-)recursive calls occurs in Algorithm 7.24 altogether? Every call generates two further recursive calls, but only up to a fixed depth k. Hence the total running time is asymptotically only 0(2k ■ n). c
Remark: The factor 2fe can be improved by more careful choice of branching. (2006: 1.2738fe)