SAT-Kodierung: Färbung von Graphen

• Knotenfärbung

  Übung: Definiere chromatische Zahl χ(G) mathend000#

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

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

• Kantenfärbung (Ramsey-Probleme)

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

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