.Petr Hliněný, FI MU Brno, 2015 1 / 24 FI: MA010: Colouring graphs
6 Colouring Graphs
One can say that the question of proper graph colouring has always been the fundamental
problem of the whole graph theory. Although, say, Euler’s theorem was older
than that, it was the famous Four colour problem in the 19th century which has since
triggered 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; edge and list colourings, graph nz. flows.
proper colouring = korektní obarvení
chromatic number = barevnost, loopless = bez smyˇcek
.Petr Hliněný, FI MU Brno, 2015 2 / 24 FI: MA010: Colouring graphs
6.1 Proper colourings of graphs
We would like to formalize a task 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(G) .✷
Definition 6.1. The chromatic number of a simple graph G, denoted by χ(G),
is the least integer χ(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).✷
• 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.
.Petr Hliněný, FI MU Brno, 2015 3 / 24 FI: MA010: Colouring graphs
Basic facts about graph colourings
• A proper graph colouring with k colours is also called a k-colouring. ✷
• A graph has a 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., χ(G) = n) iff the graph is isomorphic to complete Kn.
– every vertex can receive a different colour. . . ✷
• For any G and every subgraph H ⊆ G, it is χ(H) ≤ χ(G).
(We say that the chromatic number of a graph is subgraph-monotone.) ✷
• Every path has a proper colouring with 2 colours:
s s s s s s❢ ❢ ❢❢ ❢ ❢✷
• A cycle Cn of length n has chromatic number
– χ(Cn) = 2 if n is even,
s s
ss
❢
❢
❢
❢✷
– χ(Cn) = 3 if n is odd.
s s s s
s
s
s
❢ ❢
❢
❢ ❢
❢
?
.Petr Hliněný, FI MU Brno, 2015 4 / 24 FI: MA010: Colouring graphs
Example 6.2. Every (loopless) graph with m edges can be properly coloured with
1
2 + 2m + 1
4 colours. ✷
• If k = χ(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 χ(G) < k. ✷
• Consequently, there are at least m ≥ 1
2 k(k − 1) edges in G, and we get k ≤
1
2 + 2m + 1
4 by simple calculus. ✷ ✷
Example 6.3. If a graph G has maximum degree ∆(G) = 4, then G is 5-colourable.✷
• 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, . . .})⊆ V (G) is smallest possible. ✷
• If D = ∅, then we are done.
• Otherwise, choose w ∈ 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. ✷
independent set = nezávislá množina
.Petr Hliněný, FI MU Brno, 2015 5 / 24 FI: MA010: Colouring graphs
Independent sets
Definition: A set X ⊆ V (G) in a graph G is called an independent set of G if no
edge of G has both the ends in X (i.e., X induces no edges of G). ✷
The largest independent set size in G is denoted by α(G).
For instance, the following graph has an independent set of size 4, and no larger independent
set in this graph exists:
s s
s
s
s
s s
s
s
s
❢ ❢
❢❢
✷
Fact: Consider a proper graph colouring c : V (G) → {1, 2, . . ., k}.
• For each i ∈ {1, . . . , k}, the set c−1
(i) is independent in G. ✷
• A k-colouring of G can equivalently be described as an (ordered) partition of
V (G) into k independent sets (called colour classes) of G.
.Petr Hliněný, FI MU Brno, 2015 6 / 24 FI: 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)| (∆(G)+1).✷
Proof: Let X ⊆ V (G) be a maximum cardinality independent set in G.
– There are at most |X| · ∆(G) neighbours of X in G, and these cover all the
vertices of G, by the maximality assumption. ✷
– Hence, |V (G)| ≤ |X| + |X| · ∆(G), and |X| ≥ |V (G)| (∆(G) + 1). ✷
✷
Lemma 6.5. In any (loopless) graph G, it holds α(G) · χ(G) ≥ |V (G)|. ✷
Proof: A colouring of the graph G by k = χ(G) colours is equivalent to the existence
of a partition of V (G) into k independent sets D1 ∪ · · · ∪ Dk = V (G). ✷
Since |Di| ≤ α(G) for each 1 ≤ i ≤ k, it holds |V (G)| ≤ k · α(G). ✷
In informal words, low independence number α forces high chromatic number, and vice versa.
Though, both independence and chromatic numbers might be high.
bipartite = bipartitní, even/odd cycle = sudá/ lichá kružnice
.Petr Hliněný, FI MU Brno, 2015 7 / 24 FI: MA010: Colouring graphs
Colouring bipartite graphs
Recall that a bipartite graph is a subgraph of the complete bipartite graph Km,n for some
suitable m, n.
s s s s s
s s s s
. . .
. . . ✷
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ý, FI MU Brno, 2015 8 / 24 FI: MA010: 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).
s s s s
s
s
s
❢ ❢
❢
❢ ❢
❢
?
✷
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 ∈ V (G), and colour the vertices of G by their u-distance; ✷
– the vertices v ∈ V (G) such that dG(u, v) is even get green colour,
– the vertices w ∈ V (G) such that dG(u, w) is odd get red colour. ✷
Considering an edge vw ∈ E(G); what is the difference of dist. |dG(u, v)− dG(u, w)| ?
.Petr Hliněný, FI MU Brno, 2015 9 / 24 FI: 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. . .
s s s
s
s
s
s
s
s
s
u
v
w
v′
– By the triangle inequality, |dG(u, v) − dG(u, w)| = a ∈ {0, 1}. ✷
– If a = 1, then the distance to v and w are of diff. parity, giving diff. colours; OK.
– If a = 0, then dG(u, v) = dG(u, w) and we get a contradiction by the following.✷
Claim : If dG(u, v) = dG(u, w) for any u ∈ V (G) and an edge vw ∈ E(G), then G
has an odd cycle.
s s s
s
s
s
s
s
s
u
v
w
❢
❢
❢
u′
Choose u′
such that dG(u′
, v) = dG(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 2dG(u′
, v) + 1. ✷
* Problém ˇctyˇr barev *
.Petr Hliněný, FI MU Brno, 2015 10 / 24 FI: MA010: Colouring graphs
6.2 Motivation and applications of graph colouring
• The historical motivation (19th century)
comes from colouring maps;
→ the famous Four Colour Problem.
(Read more about planar graphs in Lecture 7.)✷
• 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.)
map colouring = barvení mapy
.Petr Hliněný, FI MU Brno, 2015 11 / 24 FI: MA010: Colouring graphs
Example 6.7. What is the correspondence between proper graph and map colourings?
a
b c
d e
f
g
h
s
s s
s s
s
s
s
a
b
c
d
e
f
g
h
✷
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:
2
1 2
3 1
2
3
1
s
s s
s s
s
s
s
2
1
2
3
1
2
3
1
✷
uniform job assignment = uniformní pˇridˇelování úkol˚u
.Petr Hliněný, FI MU Brno, 2015 12 / 24 FI: 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. ✷
A sample input:
s s
s s s s
s s s s
s s
1
2
4
3
7
10
5
6
12
11
9
8
• From this nice picture, an obvious solution is for 4 workers.
However, is 4 optimal? ✷Yes, 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.
✷
greedy algorithm = hladový algoritmus
.Petr Hliněný, FI MU Brno, 2015 13 / 24 FI: 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, . . .).✷
s s
s s
s s
s s s s
s s1
2
1
3
4
2
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. ✷
.Petr Hliněný, FI MU Brno, 2015 14 / 24 FI: 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 ∆(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 ≥ χ(G) − 1. ✷
Proof: Consider a minimal (or smallest) subgr. H ⊆ G such that χ(H) = χ(G) = k.
If δ(H) ≥ k − 1, then we are done. So, assume there is a vertex u ∈ V (H) of degree
dH(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 − 1)-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 − 1)-colourable. This contradicts χ(H) = χ(G) = k.
✷ ✷
Corollary 6.11. If every subgraph of a (loopless) graph G has a vertex of degree ≤ k
within this subgraph, then G is (k + 1)-colourable.
k-degenerate = k-degenerovaný graf
.Petr Hliněný, FI MU Brno, 2015 15 / 24 FI: 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 within this subgraph, then G is (k + 1)-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. . . )
s s
ss
s
s
s
s
s ❀
s s
ss
s ❀ s
✷
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 ∈ V (G) such that
dG(u) ≤ k and the subgraph G \ u is k-degenerate.
.Petr Hliněný, FI MU Brno, 2015 16 / 24 FI: MA010: Colouring graphs
On degenerate graphs
Proposition 6.12. (repeated) A graph G is k-degenerate iff there exists u ∈ V (G)
such that dG(u) ≤ k and the subgraph G \ u is k-degenerate.
s s
ss
s
s
s
s
s ❀
s s
ss
s
s
s
s
Proof: The forward “only if” direction is very easy: the vertex u of degree ≤ k is
directly defined by the condition of k-degeneracy of G, and G \ u is a subgraph of G.✷
Conversely, assume G \ u is k-degenerate. Let H ⊆ G be a subgraph.
– If u ∈ V (H), then we use dH(u) ≤ dG(u) ≤ k.
– If u ∈ V (H), then H contains other vertex of degree ≤ k in H since G\u ⊇ H.✷
✷
Corollary 6.13. A connected graph is a tree iff it is 1-degenerate.
s
s
ss
s
s
s
s
.Petr Hliněný, FI MU Brno, 2015 17 / 24 FI: MA010: Colouring graphs
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 ∈ V (G) of the minimum degree; dG(u) ≤ k.
• Solve the problem (colouring) recurs. for the k-degenerate subgraph G′
:= G\u.✷
• Choose the colour of u from those elements of {1, 2, . . ., k + 1} not occuring
among the neighbours of u (since there are ≤ k neighbours). ✷
Example 6.16. When “greedy” Algorithm 6.15 fails to find the chromatic number.
Consider possible greedy colouring of the following bipartite graph. . .
s
s
s
s s
s
s
s
s
s
❢
❢
✷
s
s
s
s s
s
s
s1
2
2
1 2
1
1
2
3
If we have “bad luck”, the colours of the two resulting 4-cycles do not match, and then
we have to use a third colour (on the marked vertices on the left). ✷
.Petr Hliněný, FI MU Brno, 2015 18 / 24 FI: MA010: Colouring graphs
Brooks’ theorem
The following claim strengthens Theorem 6.14 by just a “tiny bit”, and yet it is much harder. . .
Theorem 6.17. Let G be a connected loopless graph of max. degree k = ∆(G) ≥ 2.
Then χ(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+1) = 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).✷
• 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 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 − 1)-degenerate.
– Suppose not, having H1 ⊆ H with δ(H1) ≥ k. Hence w ∈ V (H1). Take a
path Q from w to V (H1 \ u) in connected G\ {u, v}. Then the terminal of
Q in H1 \ u has degree at least δ(H1) + 1 = k + 1 in G, a contradiction. ✷
• Consequently, H can be k-coloured using Theorem 6.14. 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ý, FI MU Brno, 2015 19 / 24 FI: 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 α(G); by Lemma 6.5. ✷
• Graphs constructed by iterating the following claim:
Proposition 6.18. Let G be a loopless graph. If G1 results from G by adding a new
vertex w adjacent to all the vertices of G, then χ(G1) = χ(G) + 1. ✷
Proof: It holds χ(G1) ≤ χ(G)+1 since the new vertex w gets a new colour. Conversely,
in an optimal colouring of G1, the colour of w is not repeated anywhere else, and hence
the subgraph G is (χ(G1) − 1)-coloured. ✷ ✷
• 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?✷
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. (Erdős) 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ý, FI MU Brno, 2015 20 / 24 FI: MA010: Colouring graphs
The Mycielski construction
The proof of Erdős’ 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 χ(H) =
χ(G) + 1, and H is triangle-free if G was such.
✷
The construction, formally:
– Let V (G) = {v0, v1, . . . , vn}. Set V (H) = V (G) ∪ {u0, u1, . . . , un} ∪ {w}. ✷
– Make the neighbourhood of each ui the same as that of vi. Join w to u0, . . . , un.✷
Proof (sketch): If vi gets the same colour as w in H, then vi can be (safely) recoloured
to the colour of ui. ✷Therefore, χ(G) ≤ χ(H) − 1, and the converse is trivial. ✷
edge colouring = hranové barvení, hranová barevnost
.Petr Hliněný, FI MU Brno, 2015 21 / 24 FI: 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 χe(G) 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 following theorem gives a sharp approximation of edge chromatic number.
Theorem 6.22. (Vizing) If G is a simple graph, then ∆(G) ≤ χe(G) ≤ ∆(G) + 1. ✷
For most of graphs, it actually holds ∆(G) = χe(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).
choosability = výbˇerová (ˇci listová) barevnost
.Petr Hliněný, FI MU Brno, 2015 22 / 24 FI: 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. List chromatic number (choosability) of a graph G.
Given is a graph G with an assignment of “colour lists” L : V (G) → Æ
k (k-element
subsets of colours). The task is to find a list colouring cch(V (G)) → Æ such no two
adjacent vertices receive the same colour, and cch(v) ∈ 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 list chromatic number (or choosability) ch(G)
of the graph G. ✷
Choosability can generally be much higher than the ordinary chromatic number.
Proposition 6.24. For every integer k there exists a bipartite (chromatic number 2)
graph of list chromatic number greater than k.
.Petr Hliněný, FI MU Brno, 2015 23 / 24 FI: MA010: Colouring graphs
6.5 Appendix: Nowhere zero graph flows
Recall:
• A flow f : 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.✷
Definition: For an undir. graph G, an orientation G is a digraph on V (G) = V (G) s.t.✷
– if uv ∈ E(G), then (u, v) ∈ E(G) or (v, u) ∈ E(G);
– if (u, v) ∈ E(G), then uv ∈ E(G) but (v, u) ∈ 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. k-flow) in a graph G is
– an orientation G of G, together with ✷
– a circulation f : E(G) → Z in G such that |f(e)| ∈ {1, 2, . . ., k} for all e ∈
E(G).
s s
ss
1
1
2
−1
−1
.Petr Hliněný, FI MU Brno, 2015 24 / 24 FI: MA010: Colouring graphs
Understanding nz. graph flows
s s
ss
1
1
2
−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(G) to opposite (v, u) simply inverts the flow value f(v, u) = −f(u, v).