Graph Coloring
Gegeben ist ein Graph und eine Zahl k. Gefragt ist ob die Knoten des Graphs mit k verschiedenen Farben gefärbt werden können, sodass keine benachbarten Knoten dieselbe Farbe haben.
List Coloring
Gegeben ist ein Graph und eine Liste die jedem Knoten eine Menge an möglichen Farben zuordnet. Die Frage ist im Prinzip dieselbe wie beim Graph Coloring nur dass die möglichen Farben für jeden Knoten begrenzt sind.
Student, Punkte: 130