SAT-Kodierung: Färbung von Graphen

• Knotenfärbung

  Übung: Definiere chromatische Zahl χ(G)

  Übung: welche Aussage kann man (mit polynomiellem Aufwand in | G| und c) SAT-kodieren, welche nicht:

  χ(G)≤c, χ(G)≥c

• Kantenfärbung (Ramsey-Probleme)

  Def: R(s₁,…, s_c) : = min{n | jede Kanten-c-Färbung des K_n enthält einen K_s1 der Farbe 1 oder ...oder einen K_sc der Farbe c }.

  Ü: beweise mittels SAT-Kodierung: R(4, 4)≥18, R(3, 3, 3)≥17 (und Gleichheit durch Nachdenken)