Colouring Graphs
One can say that graph colouring has always been the fundamental problem of the whole graph theory—already since mid 19th century. Although, say, Euler's theorem had been older, it was the famous Four colour problem which triggered (since 19th century) the development of nearly every branch of modern graph theory.
Brief outline of this lecture
• Definition of a proper colouring of a graph. Basic properties.
• Motivation and applications of graph colouring; map colouring.
• Further properties of the chromatic number.
• Some variants of the colouring problems; edge and list colourings, graph nz. flows.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
6.1   Proper Colourings of Graphs
How to formally formulate the requirement that adjacent objects should receive distinguishing colours?
Definition: A (proper) colouring of a graph G with k colours is an assignment of "colours" to the vertices such that every pair of adjacent vertices gets distinct colours;
c : V(G) ->• {1, 2,..., k} a function s.t. c(u) ^ c(v) for all uv e E(G) .□
Definition 6.1. The chromatic number of a simple graph G, denoted by x(G), is the least integer x(G) — k such that G can be properly coloured with k 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).n
• Notice that proper colourings and the chromatic number make sense only for loopless graphs! Parallel edges, on the other hand, do not matter at all.
□
proper coCourinjj = kprck^tm oSarvmi 6er = Sarevtiost,  CoopUss = 6ez snnjcck..
Basic facts about graph colourings
• A proper graph colouring with k colours is also called a k-colouring. □
• A graph has 1-colouring iff it has no edges (it is edgeless). □
• Every (loopless!) n-vertex graph can be properly coloured with n colours. This is optimal (i.e., x(G) — n) iff the graph is isomorphic to complete Kn.
— every vertex can receive a different colour... □
• For any G and every subgraph H C G, it is x(H) < x(G)-(We say that the chromatic number of a graph is subgraph-monotone.) □
Every path has a proper colouring with 2 colours:
®-^®-®-
-®-®-®
A cycle Cn of length n has chromatic number
x(Cn) — 2 if n is even, x(Cn) — 3 if n is odd.
-9
®-
-®
®-®-®-®
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
Example 6.2.   Every (loopless) graph with m edges can be properly coloured by
• If k — x(G) is the least number of colours in a proper colouring of G, then for each pair of colours 1 < i < j < k there is an edge with the ends coloured by i and j. Otherwise, one could join the colours i, j into one, getting x(G) < k. □
Example 6.3. If a graph G has maximum degree A(G) — 4, then G is 5-colourable.a
• Among all proper colourings of G choose one c : V(G) —>• {1, 2, 3,...} which minimizes the number of vertices of colours other than 1,2,3,4, 5.
- In other words, the set D — c_1({6, 7,... })C V(G) is smallest possible. □
• If D — 0, then we are done.
• Otherwise, choose w G D. The at most four neighbours of w in G carry at most four of the colours 1, 2, 3,4, 5, say, missing the colour 1. □
Setting the colour of w to 1 gives a proper colouring of G, too. This contradicts the choice of c minimizing D. C
I + J 2m + j colours. □
• Consequently, there are at least m > \k(k — 1) edges in G, and we get k <
Z
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
^Independent Sets in Graphs
Definition: A set X C V(G) in a graph G is called an independent set of G if no edge of G has both the ends in X (X induces no edges of G). □
The largest independent set size in G is denoted by a(G).
For instance, the following graph has an independent set of size 4, and no larger independent set in this graph exists:
Fact: Consider a proper graph colouring c : V(G) —>• {1, 2,..., k}.
• For each i e {1,..., k}, the set c_1(z) is independent in G. □
• A fc-colouring of G can equivalently be described as an (ordered) partition of V(G) into k independent sets (called colour classes) of G.
independent set= nezávisia množina
Petr Hlinený,   Fl MU Brno,  2014 5/33 Fl: MA010: Colouring graphs
Some properties of independent sets
The following simple properties are crucial for understanding the role of independent sets in graph colouring problems.
Lemma 6.4. Every graph G contains an independent set of size > \V(G)\/(A(G) + l)a Proof: Let X C V(G) be a maximum cardinality independent set in G.
- There are at most \X\ ■ A(G) neighbours of X in G, and these cover all the vertices of G, by the maximality assumption. □
- Hence, \V(G)\ < \X\ + \X\ • A(G), and \X\ > \V(G)\/(A(G) + 1). □
c
Lemma 6.5. In any (loopless) graph G, it holds a(G) ■ x(G) > \V(G)\. c
Proof: A colouring of the graph G by k — x(G) colours is equivalent to the existence of a partition of V(G) into k independent sets D\ U • • • U D]~ — V(G). □
Since \Di\ < a(G) for each 1 < i < k, it holds \V(G)\ < k ■ a(G). C In other words, low independence number a forces high chromatic
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
Colouring Bipartite Graphs
Recall that a bipartite graph is a subgraph of the complete bipartite graph Km,n for any (suit.) m, n.
Fact: A simple graph G is bipartite if and only if G has a proper 2-colouring. □
• Every tree is bipartite. □
• Every even cycle is bipartite. □
• No odd cycle is bipartite.
Petr Hliněný,   Fl MU Brno, 2014
Bipartite = úipartžtní,  even/oddcycíe = sudá/íichá pružnice
Fl: MAO 10: Colouring graphs
Graphs with no odd cycles
Theorem 6.6. A graph G is 2-colourable (bipartite) if, and only if, G contains no cycle of odd length (no odd cycle).
?
This is another beautiful example of a good characterization:
- a graph containing an odd cycle is clearly not bipartite, and
- an absence of this one obvious obstacle already implies bipartiteness! □
Proof: Assume G is connected (or, colour each component separately). The "only if" direction is trivial since an odd cycle is not 2-colourable.   For the "if" direction...
Choose any u G V(G), and colour the vertices of G by their w-distance; □
- the vertices v G V(G) such that dc(u,v) is even get green colour,
- the vertices w G V(G) such that dc(u,w) is odd get red colour. □
Considering an edge vw G E(G); what is the diff. of distances \dc(u, v) — dc(u, w)\ 1
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
Theorem 6.6. (repeated) A graph G is 2-colourable (bipartite) if, and only if, G contains no cycle of odd length (no odd cycle).
Proof continued...
- By the triangle inequality, \dc(u, v) — dc(u, w)\ — a e {0,1}. □
- If a — 1, then the distance to v and w are of diff. parity, giving diff. colours; OK.
- If a — 0, then da(u, v) — da(u, w) and we get a contradiction by the following.□
Claim : If da(u,v) — da(u,w) for any u e V(G) and an edge vw G E(G), then G has an odd cycle.
-----® w
u'
u •-----•----
-----® V
Choose u' such that da(u',v) — da(u',w) is smallest possible. □
Then the shortest paths from u' to v and to w have to be disjoint except at u', giving a cycle of an odd length 2da(u', v) + 1. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
Motivation and Applications of Graph Colouring
The historical motivation (19th century) comes from colouring maps; Mt
the famous Four Colour Problem.
(Read more in Lecture 8.)n
Imagine the task to schedule a bunch of meetings
of groups with mutual conflicts (e.g., a same person in several groups).
- What is the shortest time span all the meetings can take place in? □
- The vertices of our graph are the groups,
time slots are the colours, and (pairwise) conflicts are the edges.
- A shortest time span is proportional to the number of used colours. □
Similarly, imagine the following uniform job assignment task:
- each job comes in as a time interval [si,ti], and
- no two overlapping jobs may be assigned to the same worker. □
This again leads to the problem of a proper colouring (colours ~ the workers) of the "intersection graph" of the job intervals. (Read more about intersection graphs in Lecture 9.)
Example 6.7.   What is the correspondence between proper graph and map colourings?
In the graph;
- the vertices represent the map regions (which are assumed to be "in one piece"),
- the edges are neighbbouring pairs of regions (sharing a section of a boundary).
One may or may not include the "outer region"... □
A solution to both of the colouring problems is identical:
Z
map cotouring = Barvení mapy
Petr Hliněný,   Fl MU Brno,   2014 11/33 Fl: MA010: Colouring graphs
Example 6.8. A uniform job assignment problem.
Assume a given list of jobs, each one having specified release and end time (i.e. represented by intervals on the time axis). The task is to assign workers to these jobs such that the total number of workers is minimized. All the workers and jobs are uniform. □
An example of the input: g g
13 5 11 •-• •-•
2 7 8 12 •-•   •-•
4 10
• From this nice picture, an obvious solution is for 4 workers.
However, is 4 optimal? nYes, one can see 4 pairwise overlapping intervals. □
• So, what is the general case?
We aim to show that this is another nice example of a good characterization: □
- either we can partition all jobs into k "layers" of nonoverlapping intervals,
- or there is a point at which at least k + 1 intervals overlap. □
The proof is given next.
uniform joB assignment = uniformní přidělování úkolů
Petr Hliněný,   Fl MU Brno,   2014 12/33 Fl: MA010: Colouring graphs
Algorithm 6.9. Greedy algorithm for the uniform job assignment problem.
(In the terminology of Lecture 9, for optimal proper colouring of interval graphs.)
The problem of Example 6.8 is optimally solved by the following "greedy" assignment:
1. We sort the jobs by their release times (i.e., the intervals by their left endpoints).
2. For every subsequent job, we assign the least available worker (among 1,2,... ).n
4 •-•
3 •-•
2 •-•    •-• 2
1 •-•   1 •-•
Proof: Let this algorithm use k workers in total. We easily prove that no less than k workers suffice. So, at what moment the worker of number k started to work? □
At a moment when all workers 1, 2,..., k — 1 have been busy with other jobs. Hence k jobs mutually overlap at that moment, proving the required. C
Petr Hliněný,   Fl MU Brno, 2014
greedy algorithm = hladový algoritmus
Fl: MA010: Colouring graphs
6.3   Properties of the Chromatic Number
Colouring and vertex degrees
• Easily (Example 6.3); any graph G can be prop, coloured with A(G) + 1 colours.□
• A converse does not hold—a bipartite graph is 2-colourable while its maximum and also minimum degrees grow arbitrarily. □
• Still, the following is rather easy and very useful:
Lemma 6.10. Every graph G has a subgraph of minimum degree > x(G) — 1. □
Proof: Consider a minimal (or smallest) subgr. H C G such that x(H) — x(G) — k.
If 6(H) > k — 1, then we are done. So, assume there is a vertex u e V(H) of degree dii(u) < k — 2 (the degree in H). Then u has at most k — 2 neighbours in H. □
By the minimality of H, the smaller subgraph H — u is (k— l)-colourable, and u "sees" only < k — 2 out of those colours in its neighbours. Hence a proper colour can be chosen for u, too, and H is (k — l)-colourable. This contradicts x(H) — x(G) — k.
C
Corollary 6.11. If every subgraph of a (loopless) graph G has a vertex of degree < k, then G is (k + l)-colourable.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
^Degenerate Graphs and Greedy Colouring
Corollary 6.11. (repeated) If every subgraph of a (loopless) graph G has a vertex of degree < k, then G is (k + l)-colourable.
The previous claim directly motivates the following classical notion:
Definition: A graph G is k-degenerate if every subgraph of G contains a vertex of degree at most k (meaning the degree in the subgraph). □
The following graph is 2-degenerate. Though, how can we quickly verify its degeneracy, checking "every subgraph"?  (Note; it is not enough to have some degree-2 vertices...)
□
It is actually enough to find an "elimination ordering" of all the vertices, thanks to:
Proposition 6.12. A graph G is k-degenerate iff there exists u e V(G) such that do(u) < k and the subgraph G\u is k-degenerate.
k -degenerate = k -degenewvamj graf
Petr Hlinený,   Fl ML) Brno,   2014 15/33 Fl: MA010: Colouring graphs
On degenerate graphs
Proposition 6.12. A graph G is /j-degenerate iff there exists u e V(G) such that da(u) < k and the subgraph G \ u is fc-degenerate.
Proof: The forward "only if" direction is trivial. □
Conversely, assume G \ u is fc-degenerate. Let H C G be a subgraph.
- If m G       ), then we use (1h{u) < da(u) < k.
- If u ^ V(H), then H contains another vertex of degree < k in H since G\u D
is fc-degenerate. □ C
Corollary 6.13. /4 connected graph is a tree iff it is l-degenerate.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
On greedy graph colouring
Theorem 6.14. Let k > 1. Every k-degenerate loopless graph can be properly coloured by k + 1 colours. □
The proof is immediately given by the following algorithm: Algorithm 6.15. Greedy colouring of a k-degenerate graph G.
• Find a vertex u e V(G) of the minimum degree; dc(u) < k.
• Solve the problem (colouring) recurs, for the k-degenerate subgraph G' :— G\u.n
• Choose the colour of u from those elements of {I, 2,..., k + 1} not occuring on the < k neighbours of u. □
Example 6.16. When "greedy" Algorithm 6.15 fails to find the chromatic number. Consider possible greedy colouring of the following bipartite graph...
3
If we have "bad luck", the colours of the two resulting 4-cycles do not match, and then we have to use a colour 3 (the vert, marked on the left). C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
Brooks' Theorem
The following claim strengthens Theorem 6.14 just by a "tiny bit", and yet it is much harder...
Theorem 6.17. Let G be a connected loopless graph of max. degree k — A(G) > 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 6.6.
Let k > 3 from now on. In one direction, \(Kk+i) — k+1 (the claimed exception). □
Otherwise, assume that G is not complete. Furthermore, all degrees in G are equal to k (since the greedy approach of Alg. 6.15 could be applied to vertices of deg. < k).u
• 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 its parts separately by inductions
• 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)-degenerate.
- Suppose not, having Hi C H with S(Hi) > k. Hence w ^ V(Hi). Take a path Q from w to V(H\ \ u) in connected G — {u, v}. Then the terminal of Q in Hi \ u has degree at least 6(Hi) + 1 = A; + 1 in G, a contradiction. □
• Consequently, H can be fc-coloured using Theorem 7.7. After we "split u" 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 < k can be chosen for w. ^
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
Graphs of High Chromatic Number
Which graphs are of high chromatic number? For example...
• The complete graphs Kn for high n. □
• Graphs G with (relatively) small a(G); by Lemma 6.5. □
• Graphs constructed by iterating the following claim:
Proposition 6.18. Let G be a loopless graph. IfG\ results from G by adding a new vertex w adjacent to all the vertices of G, then x(Gi) — x(G) + 1. □
Proof: It holds x(Gi) < x(G)+l since the new vertex w gets a new colour. Conversely in an optimal colouring of G\, the colour of w is not repeated anywhere else, and hence the subgraph G is (x{G\) — l)-coloured. □ C
• Though, all the previous examples involve, in some more or less explicit way, large cliques as subgraphs. Is high chromatic number related to cliques in both ways?n No, this is very far from the truth, as far as the following incredibly strong (and not so easy to prove) statement:
Theorem 6.19. (Erdos) 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.
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
The Mycielski construction
The proof of Erdos' Theorem 6.19 is not only involved, but also non-constructive, and so quite hard to really "grasp" the claim. On the other hand, the following weaker claim is rel. easier.
Proposition 6.20. (Mycielski) Let G be a loopless graph. The graph H obtained from G by the following sketched construction has the chromatic number x{H) — x(G) + 1, and H is triangle-free if G was such.
The construction, formally:
- LetV(G) = {vQ,v1,...,vn}. SetV(H) = V(G)U{u0,Ul,...,un}U{w}. □
- Make the neighbourhood of each Ui the same as that ofvi. Join w to uo, ...,«„.□
Proof (sketch): If Vi gets the same colour as w in H, then Vi can be (safely) recoloured to the colour of Ui. ^Therefore, x(G) < x(H) ~ 1> ar|d the converse is trivial. C
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs
6.4   Other Variants of Graph Colouring
For start, we look at the case in which not vertices, but edges receive colours.
Definition 6.21. The edge chromatic number Xe(G) of a graph G.
We are looking for an edge colouringce(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 Xe(G). □
The theorem of Vizing gives a sharp approximation of edge chromatic number.
Theorem 6.22. If G is a simple graph, then A(G) < Xe(G) < A(G) + 1. □
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 (as edge colouring of planar bridgeless graphs).
Petr Hliněný,   Fl MU Brno, 2014
edge coíouring = (vránové Barvení, hranová Barevnost
Fl: MA010: Colouring graphs
Selecting colours from distinct lists
For another view, imagine that the colours of vertices are not selected from a global pool, but instead from separate (local) lists at each vertex.
Definition 6.23. 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 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. □
Choosability (surprise?) can generally be much higher than ordinary chromatic number.
Proposition 6.24. For every integer k there exists a bipartite (chromatic number 2) graph of choosability greater than k.
Petr Hliněný,   Fl MU Brno, 2014
cfioosaúititii = víéhová (či Ostává) Barevnost
Fl: MA010: Colouring graphs
6.5   Appendix: Nowhere Zero Graph Flows
Recall:
• A flow / : E(G) —>• R in a network G satisfying the flow conservation constraint at all the vertices including the source and the sink, is called a circulation in G.o
Definition: For an undir. graph G, an orientation G is a digraph on V(G) — V(G) s.t.n
- \fuve E(G), then (u,v) e E(G) or (v,u) e E(G);
- if (u,v) e E(G), then uv e E(G) but (v,u) g E(G).
Informally, G results from G by giving an arbitrary (one!) orientation to each of its edges. □
Definition 6.25. A nowhere-zero graph k-flow (shortly nz. fc-flow) in a graph G is
- an orientation G of G, together with □
- a circulation / : E(G)     Z in G such that |/(e)| e {1, 2,..., k} for all e e E(G).
-1
Petr Hliněný,   Fl MU Brno,   2014 23/33 Fl: MA010: Colouring graphs
Understanding nz. graph flows
-1
-1
1
How nz. k-flows compare to ordinary network flows:
• Graph flows are actually circulations, i.e., they have no source and no sink. □
• All the capacities are implicitly —k (lower) and +k (upper).
Note, flow values are always integral and negative flow values are allowed here! □
• The role of an orientation G in the definition is rather irrelevant; changing from
(u, v) e E(G) to opposite (v, u) simply inverts the flow value f(v, u) — —f(u, v).
Petr Hliněný,   Fl MU Brno, 2014
Fl: MA010: Colouring graphs