Outline

• Graph colourings and chromatic number
  definition of a proper colouring, chromatic number, basic properties and two-colourable (bipartite) graphs, k-degenerated graphs and greedy colouring, graphs of high chromatic number
  
• Other related problems
  edge colouring and chromatic index, Vizing theorem, list colouring (choosability), Hamiltonian paths and cycles
• NP-complete problems on graphs
  3-colourability, independent set, vertex cover, dominating set, Hamiltonian circuit, etc
  
• The vertex-cover story
  some parameterized algorithms for the k-vertex cover problem

Goals

While the previous lectures mentioned numerous applications of graph theory in computer science which have efficient solutions, this lecture shows the opposite side -- graph problems which are NP-complete ("hopeless"). Prominent such a problem is the colourability one (and its variants), others include the Hamiltonian cycle/path, independent set, vertex cover, etc. Since especially the colourability problem has been a strong driving force of development of the whole graph theory since 19th century, we pay a special attention to it here and in the next lecture.

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

Again, the content of this lecture is not much covered by this textbook. However, read the definition of the graph colouring problem in Section 6.4. See the provided online references, or read Chapter 5 of Diestel's textbook for advanced study.