List colourings of planar graphs |
| |
Authors: | Margit Voigt |
| |
Institution: | Institut für Mathematik, TU Ilmenau, O-6300 Ilmenau, Germany |
| |
Abstract: | A graph G = G(V, E) is called L-list colourable if there is a vertex colouring of G in which the colour assigned to a vertex v is chosen from a list L(v) associated with this vertex. We say G is k-choosable if all lists L(v) have the cardinality k and G is L-list colourable for all possible assignments of such lists. There are two classical conjectures from Erd
s, Rubin and Taylor 1979 about the choosability of planar graphs: every planar graph is 5-choosable and, there are planar graphs which are not 4-choosable.
We will prove the second conjecture. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|