Die Einführung des VIVO-Systems an der HTWD befindet sich derzeit in der Testphase. Daher kann es noch zu anwendungsseitigen Fehlern kommen. Sollten Sie solche Fehler bemerken, können Sie diese gerne >>hier<< melden.
Sollten Sie dieses Fenster schließen, können Sie über die Schaltfläche "Feedback" in der Fußleiste weiterhin Meldungen abgeben.
Vielen Dank für Ihre Unterstützung!
A not 3-choosable planar graph without 3-cycles
Artikel
An
L-
list
coloring of a graph
G is a proper vertex coloring in which every vertex
v receives a color from a prescribed list
L(
v).
G is called
k-
choosable if all lists
L(
v) have the cardinality
k and
G is
L-list colorable for all possible assignments of such lists.
Recently, Thomassen has proved that every planar graph with girth greater than 4 is 3-choosable. Furthermore, it is known that the chromatic number of a planar graph without 3-cycles is at most 3. Consequently, the question resulted whether every planar graph without 3-cycles is 3-choosable.
In the following we will give a planar graph without 3-cycles which is not 3-choosable.