Discrete Math › Section C · Graph theory › Topic C.6
Coloring graphs
How few exam slots can a college use so that no student has two exams at once? How few colours does a map need? Both are graph colouring problems, and they lead from quick counting arguments to one of the most famous computer-assisted proofs in mathematics.
In this topic
- Conflicts as edges
- Proper colourings and the chromatic number
- Graphs you can colour at a glance
- Lower bounds: cliques
- Upper bounds: greedy colouring and Brooks' theorem
- Worked example: scheduling six exams
- Worked example: when greedy and cliques mislead
- Maps and the four colour theorem
- Colouring edges
- Common mistakes to avoid
- Key takeaways
This topic is part of Wuanberri Pro. Checking your access…