Graph colouring
Colouring the vertices of a graph so that two neighbours differ: chromatic number, bounds from cliques and the maximum degree, greedy colouring and vertex order, bipartite graphs, and timetabling problems seen as colourings.
- 28 cards
- 6 topics
- Free
The outline, topic by topic
Each topic is weighted the way the exam weighs it.
- Concepts
- Questions
- Sort and link
- The numbers
- Scenarios
- Understand
A few cards from the deck
Proper colouring: what is it?
Show the answer
An assignment of one colour to each vertex such that two neighbouring vertices never get the same one.
A single edge whose two ends share a colour is enough to make it invalid: check edge by edge.
How many colours does this program use to colour the path A-B-C-D?
```python
adj = {"A": ["B"], "B": ["A", "C"], "C": ["B", "D"], "D": ["C"]}
color = {}
for v in ["A", "D", "B", "C"]:
used = {color[w] for w in adj[v] if w in color}
c = 0
while c in used:
c += 1
color[v] = c
print(len(set(color.values())))`3241
Show the answer
3A and D get 0, B gets 1, then C sees B (1) and D (0) and has to take 2. In the order A, B, C, D the same graph would be coloured with 2 colours: the processing order matters.
A graph that contains a … of size k has a chromatic number of at least ….
Show the answer
A graph that contains a clique of size k has a chromatic number of at least k.
A triangle forces 3 colours, a K₄ forces 4. It is the lower bound you look for on the drawing.
Chromatic number: what is it?
Show the answer
The smallest number of colours with which the vertices of a graph can be coloured properly, written χ(G).
To prove that χ(G) = k you need two things: a colouring with k colours, and a proof that k − 1 colours cannot work (a clique of size k, for instance).