Outline

• Proper graph colouring; Chromatic number
  definition of a proper colouring, chromatic number, independent sets and two-colourable (bipartite) graphs
• Motivation and Applications
  classical map colourings (The Four Colour Problem), simple scheduling and assignement problems
• Properties of the chromatic number
  k-degenerated graphs and greedy colouring, Brooks theorem, graphs of high chromatic number,
• Other views of colouring problems
  other variants of colouring problems (edge and list colourings), nowhere zero graph flows....

Goals

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. Because of this fundamental importance, we define the colourability problem of graphs and its variants, and survey the basic properties with simple proofs. 

Course book  [Invitation to Discrete Mathematics (by Jiří Matoušek, Jaroslav Nešetřil)]:

Read the definition of the graph colouring problem in Section 6.4 (6.8 in the Czech edition). Refer to [Diestel] for further reading.

Advanced course book [Graph theory (by Reinhard Diestel)]:

Study relevant parts of Sections 5.1-5.4 for the colouring problems and, voluntarily, parts of 6.3-6.5 for graph flows.