Enumerating Graphs with respect to their Choosability

Abstract

In dieser Arbeit zeigen wir neue Ansätze, um Graphen zu enumerieren, bei denen die Listenfärbbarkeit nicht mit der Färbbarkeit übereinstimmt. Zunächst enumerieren wir die kleinsten Graphen, die 3-färbbar sind, aber nicht 3-listenfärbbar sind. Dazu führen wir zwei Methoden zusammen: Wir bauen auf der sogenannten “Vetting Methode” auf, welche das Kernstück bekannter Algorithmen ist, um die Listenfärbbarkeit von Graphen zu bestimmen. Diese integrieren wir in SMS, einem Framework, welches gut geeignet ist, um mittels logischer Formeln darstellbare Graphenklassen zu enumerieren. Um die untere Schranke für den kleinsten planaren Graphen, der nicht 4-listenfärbbar ist, zu erhöhen, finden wir neue Bedingungen für solche Graphen und verbessern die Laufzeit bisheriger Tests signifikant. Dadurch können wir zeigen, dass der kleinste planare, nicht4-listenfärbbare Graph, mindestens 27 Knoten hat. Gleichzeitig finden wir einen planaren Graphen mit 27 Knoten, der nicht durch momentane Methoden als 4-listenfärbbar verifiziert werden kann, und stellen eine neue Methode vor, bei der dies gelingt.

This thesis shows new approaches to enumerating graphs where the list chromatic number does not coincide with the chromatic number. To begin with, we enumerate the smallest graphs that are 3-colorable but not 3-choosable. We base this approach on two existing methods: The “Vetting Method” is the crucial part of known algorithms to compute the list chromatic number. We integrate this method into SMS, a framework that is well suited for enumerating classes of graphs that can be expressed as logical formulas. In order to raise the lower bound for the size of planar graphs that are not 4-choosable, we find new conditions for such graphs and improve the runtime of known tests significantly. This allows us to show that the smallest planar graph that is not 4-choosable must have at least 27 vertices. We find a planar graph with 27 vertices where current methods cannot show its 4-choosability, so we introduce a new method that succeeds.