List colourings of planar graphs
List colourings of planar graphs
复制标题
DOI：
10.1016/0012-365x(93)90579-i
复制
发表时间：
2006-05
期刊：
影响因子：
--
通讯作者：
M. Voigt
中科院分区：
文献类型：
--
作者：
M. Voigt
图G=G（V，E）被称为L-list colorableable，如果有一个顶点的颜色为gin，该顶点的颜色是从与该顶点相关联的listL(V)中选择的。如果所有的列表l (v)都具有基数，并且L-list对于这些列表的所有可能赋值都是可着色的，我们就说它是可着色的。关于平面图的可选性，Erdős， Rubin和Taylor 1979年提出了两个经典的猜想：(1)所有的平面图都是可5选的，(2)不存在可4选的平面图。我们将证明第二个猜想。
A graphG=G(V,E) is called L-list colourableif there is a vertex colouring ofGin which the colour assigned to a vertexvis chosen from a listL(v) associated with this vertex. We sayGisk-choosableif all listsL(v) have the cardinalitykandGis 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:(1)every planar graph is 5-choosable and,(2)there are planar graphs which are not 4-choosable.We will prove the second conjecture.