✦ LIBER ✦

Star coloring planar graphs from small lists

✍ Scribed by André Kündgen; Craig Timmons

Publisher: John Wiley and Sons
Year: 2009
Tongue: English
Weight: 184 KB
Volume: 63
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20431

No coin nor oath required. For personal study only.

✦ Synopsis

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 of girth 5 that requires 6 colors to star color. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 324–337, 2010

📜 SIMILAR VOLUMES

Star coloring bipartite planar graphs

✍ H. A. Kierstead; André Kündgen; Craig Timmons 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 139 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 bipartite planar graph can be star colored from lists of size 14, and we give an example of a bipartite planar graph that requires at least eig

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

Coloring graphs from lists with bounded

Coloring graphs from lists with bounded size of their union

✍ Daniel Král'; Jiří Sgall 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 103 KB

## Abstract A graph __G__ is __k‐choosable__ if its vertices can be colored from any lists __L__(ν) of colors with |__L__(ν)| ≥ __k__ for all ν ∈ __V__(__G__). A graph __G__ is said to be (__k,ℓ__)‐__choosable__ if its vertices can be colored from any lists __L__(ν) with |__L__(ν)| ≥__k__, for all

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.

NP-completeness of list coloring and pre

NP-completeness of list coloring and precoloring extension on the edges of planar graphs

✍ Dániel Marx 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 110 KB

## Abstract In the edge precoloring extension problem, we are given a graph with some of the edges having preassigned colors and it has to be decided whether this coloring can be extended to a proper __k__‐edge‐coloring of the graph. In list edge coloring every edge has a list of admissible colors,