✦ LIBER ✦

Acyclic 5-choosability of planar graphs without adjacent short cycles

✍ Scribed by O. V. Borodin; A. O. Ivanova

Publisher: John Wiley and Sons
Year: 2010
Tongue: English
Weight: 93 KB
Volume: 68
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20549

No coin nor oath required. For personal study only.

✦ Synopsis

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-cycle where 3 ≤ j ≤ 5 if i = 3 and 4≤ j ≤ 6 if i = 4. This result absorbs most of the previous work in this direction.

📜 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 ϕ(_

Planar graphs without 4-cycles are acycl

Planar graphs without 4-cycles are acyclically 6-choosable

✍ Weifan Wang; Min Chen 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 190 KB

## 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__)∈_

Choosability of toroidal graphs without

Choosability of toroidal graphs without short cycles

✍ Leizhen Cai; Weifan Wang; Xuding Zhu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 142 KB 👁 1 views

## Abstract Let __G__ be a toroidal graph without cycles of a fixed length __k__, and χ~__l__~(__G__) the list chromatic number of __G__. We establish tight upper bounds of χ~__l__~(__G__) for the following values of __k__: © 2009 Wiley Periodicals, Inc. J Graph Theory 65: 1–15, 2010.