Part: Vertex Colorings and Decompositions

In this part, problems involving the colorings of the vertices in the graph will be considered. Many practical problems which can be modeled as graph-theoretical problems, can be reduced to vertex colorings problems, i.e. problems that involve splitting the set of vertices of a graph into disjoint subsets fulfilling particular properties.

  1. Theorem: Brooks' Theorem
  2. Definition: Chromatic Number and $k$-Coloring of a Graph
  3. Proposition: Chromatic Number and Maximum Vertex Degree
  4. Chapter: Colorings of Planar Graphs

Thank you to the contributors under CC BY-SA 4.0!