✦ LIBER ✦

A not 3-choosable planar graph without 3-cycles

✍ Scribed by Margit Voigt

Publisher: Elsevier Science
Year: 1995
Tongue: English
Weight: 140 KB
Volume: 146
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00180-9

No coin nor oath required. For personal study only.

✦ Synopsis

An L-list coloring of a graph G is a proper vertex coloring in which every vertex v receives a color from a prescribed list L(v). G is called k-choosable if all lists L(v) have the cardinality k and G is L-list colorable for all possible assignments of such lists.

Recently, Thomassen has proved that every planar graph with girth greater than 4 is 3-choosable. Furthermore, it is known that the chromatic number of a planar graph without 3-cycles is at most 3. Consequently, the question resulted whether every planar graph without 3-cycles is 3-choosable.

In the following we will give a planar graph without 3-cycles which is not 3choosable.

📜 SIMILAR VOLUMES

Choosability and edge choosability of pl

Choosability and edge choosability of planar graphs without five cycles

✍ Weifan Wang; Ko-Wei Lih 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 402 KB

## It is proved that a planar graph G without five cycles is three degenerate, hence, four choosable, and it is also edge-(A( G) + l)-h

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

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

On 3-colorable planar graphs without sho

On 3-colorable planar graphs without short cycles

✍ Min Chen; Weifan Wang 📂 Article 📅 2008 🏛 Elsevier Science 🌐 English ⚖ 198 KB

On 3-colorable non-4-choosable planar gr

On 3-colorable non-4-choosable planar graphs

✍ Voigt, M.; Wirth, B. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 72 KB 👁 2 views

An L-list coloring of a graph G is a proper vertex coloring in which every vertex v gets a color from a list L(v) of allowed colors. G is called k-choosable if all lists L(v) have exactly k elements and if G is L-list colorable for all possible assignments of such lists. Verifying conjectures of Erd