✦ LIBER ✦

A note on list improper coloring planar graphs

✍ Scribed by Ko-Wei Lih; Zengmin Song; Weifan Wang; Kemin Zhang

Publisher: Elsevier Science
Year: 2001
Tongue: English
Weight: 267 KB
Volume: 14
Category: Article
ISSN: 0893-9659
DOI: 10.1016/s0893-9659(00)00147-6

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G is called (k, d)*-choosable if, for every list assignment L satisfying [L(v)l = k for all v E V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. In this note, we prove that every planar graph without 4-cycles and /-cycles for some l E {5, 6, 7} is (3, 1)*-choosable.

📜 SIMILAR VOLUMES

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 |_

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

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.

On list-coloring outerplanar graphs

✍ Joan P. Hutchinson 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 162 KB

## Abstract We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors __L__ (__v__ ) for each vertex __v__ such that $|L(v)|\geq\min\{{\deg}(v),4\}$ (resp., $|L(v)|\geq{\min}\{{\deg}(v),5\}$) can be __L__‐list‐colored (except when

Sum List Coloring Graphs

✍ Adam Berliner; Ulrike Bostelmann; Richard A. Brualdi; Louis Deaett 📂 Article 📅 2006 🏛 Springer Japan 🌐 English ⚖ 137 KB

Star coloring planar graphs from small l

Star coloring planar graphs from small lists

✍ André Kündgen; Craig Timmons 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 184 KB

## Abstract A __star coloring__ of a graph is a proper vertex‐coloring such that no path on four vertices is 2‐colored. We prove that the vertices of every planar graph of girth 6 (respectively 7, 8) can be star colored from lists of size 8 (respectively 7, 6). We give an example of a planar graph