✦ LIBER ✦

List colourings of planar graphs

✍ Scribed by Margit Voigt

Publisher: Elsevier Science
Year: 1993
Tongue: English
Weight: 259 KB
Volume: 120
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(93)90579-i

No coin nor oath required. For personal study only.

✦ Synopsis

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 u is chosen from a list L(v) associated with this vertex. We say G is k-choosable if all lists L(u) have the cardinality k and G is L-list colourable for all possible assignments of such lists. There are two classical conjectures from Erd&, 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.

📜 SIMILAR VOLUMES

Total Colourings of Planar Graphs with L

Total Colourings of Planar Graphs with Large Girth

✍ O.V. Borodin; A.V. Kostochka; D.R. Woodall 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 96 KB

It is proved that if G is a planar graph with total (vertex-edge) chromatic number χ , maximum degree and girth g, then χ = + 1 if ≥ 5 and g ≥ 5, or ≥ 4 and g ≥ 6, or ≥ 3 and g ≥ 10. These results hold also for graphs in the projective plane, torus and Klein bottle.

Adapted list coloring of planar graphs

✍ Louis Esperet; Mickaël Montassier; Xuding Zhu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 1 views

## Abstract Given an edge coloring __F__ of a graph __G__, a vertex coloring of __G__ is __adapted to F__ if no color appears at the same time on an edge and on its two endpoints. If for some integer __k__, a graph __G__ is such that given any list assignment __L__ to the vertices of __G__, with |_

Set colourings of graphs

✍ Béla Bollobás; Andrew Thomason 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 584 KB

Acyclic list 7-coloring of planar graphs

✍ O. V. Borodin; D. G. Fon-Der Flaass; A. V. Kostochka; A. Raspaud; E. Sopena 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

List Edge and List Total Colourings of M

List Edge and List Total Colourings of Multigraphs

✍ O.V. Borodin; A.V. Kostochka; D.R. Woodall 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 425 KB

This paper exploits the remarkable new method of Galvin (J. Combin. Theory Ser. B 63 (1995), 153 158), who proved that the list edge chromatic number /$ list (G) of a bipartite multigraph G equals its edge chromatic number /$(G). It is now proved here that if every edge e=uw of a bipartite multigrap

3-List-Coloring Planar Graphs of Girth 5

✍ C. Thomassen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 269 KB

We prove that every planar graph of girth at least 5 is 3-choosable. It is even possible to precolor any 5-cycle in the graph. This extension implies Grötzsch's theorem that every planar graph of girth at least 4 is 3-colorable. If 1995 Academic Press, Inc.