𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Planar graphs without 4-cycles are acyclically 6-choosable

✍ Scribed by Weifan Wang; Min Chen

Publisher
John Wiley and Sons
Year
2009
Tongue
English
Weight
190 KB
Volume
61
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

A proper vertex coloring of a graph G=(V, E) is acyclic if G contains no bicolored cycle. A graph G is acyclically L‐list colorable if for a given list assignment L={L(v)|v∈V}, there exists a proper acyclic coloring π of G such that π(v)∈L(v) for all v∈V. If G is acyclically L‐list colorable for any list assignment with |L(v)|≥k for all v∈V, then G is acyclically k‐choosable. In this paper we prove that every planar graph G without 4‐cycles is acyclically 6‐choosable. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 307–323, 2009

📜 SIMILAR VOLUMES

Acyclic 5-choosability of planar graphs
Acyclic 5-choosability of planar graphs without small cycles
✍ Mickaël Montassier; André Raspaud; Weifan Wang 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 188 KB 👁 1 views

## Abstract A proper vertex coloring of a graph __G__ = (__V,E__) is acyclic if __G__ contains no bicolored cycle. A graph __G__ is acyclically __L__‐list colorable if for a given list assignment __L__ = {__L__(__v__): __v__: ∈ __V__}, there exists a proper acyclic coloring ϕ of __G__ such that ϕ(_

Acyclic 5-choosability of planar graphs
Acyclic 5-choosability of planar graphs without adjacent short cycles
✍ O. V. Borodin; A. O. Ivanova 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 93 KB 👁 1 views

The conjecture on acyclic 5-choosability of planar graphs [Borodin et al., 2002] as yet has been verified only for several restricted classes of graphs. None of these classes allows 4-cycles. We prove that a planar graph is acyclically 5-choosable if it does not contain an i-cycle adjacent to a j-cy

The 4-Choosability of Plane Graphs witho
The 4-Choosability of Plane Graphs without 4-Cycles
✍ Peter Che Bor Lam; Baogang Xu; Jiazhuang Liu 📂 Article 📅 1999 🏛 Elsevier Science 🌐 English ⚖ 179 KB

A graph G is called k-choosable if k is a number such that if we give lists of k colors to each vertex of G there is a vertex coloring of G where each vertex receives a color from its own list no matter what the lists are. In this paper, it is shown that each plane graph without 4-cycles is 4-choosa

Planar graphs without 4-cycles adjacent
Planar graphs without 4-cycles adjacent to 3-cycles are list vertex 2-arborable
✍ Oleg V. Borodin; Anna O. Ivanova 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB

## Abstract It is known that not all planar graphs are 4‐choosable; neither all of them are vertex 2‐arborable. However, planar graphs without 4‐cycles and even those without 4‐cycles adjacent to 3‐cycles are known to be 4‐choosable. We extend this last result in terms of covering the vertices of a