✦ LIBER ✦

Every Planar Graph Is 5-Choosable

✍ Scribed by C. Thomassen

Publisher: Elsevier Science
Year: 1994
Tongue: English
Weight: 56 KB
Volume: 62
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1994.1062

No coin nor oath required. For personal study only.

✦ Synopsis

We prove the statement of the title, which was conjectured in 1975 by V. G. Vizing and, independently, in 1979 by P. Erdös, A. L. Rubin, and H. Taylor. (i) 1994 Academic Press, Inc.

📜 SIMILAR VOLUMES

Every 2-choosable graph is (2m, m)-choos

Every 2-choosable graph is (2m, m)-choosable

✍ Tuza, Zs.; Voigt, M. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 449 KB

A graph G = (V, E ) with vertex set V and edge set E is called (a, b)-choosable ( a 2 2b) if for any collection {L(w)lv E V} of sets L ( v ) of cardinality a there exists a collection Giving a partial solution to a problem raised by Erdos, Rubin, and Taylor in 1979, we prove that every (2. 1)-choos

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

A sufficient condition for planar graphs

A sufficient condition for planar graphs to be acyclically 5-choosable

✍ Min Chen; André Raspaud 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 216 KB 👁 1 views

## Abstract A proper vertex coloring of a graph __G__ = (__V, E__) is acyclic if __G__ contains no bicolored cycle. Given a list assignment __L__ = {__L__(__v__)|__v__∈__V__} of __G__, we say __G__ is acyclically __L__‐list colorable if there exists a proper acyclic coloring π of __G__ such that π(

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

Every connected graph is a query graph

✍ Peter M. Winkler 📂 Article 📅 1987 🏛 John Wiley and Sons 🌐 English ⚖ 173 KB

Let Vbe a set of bit strings of length k, i.e., V C {0, l}'. The query graph Q ( V ) is defined as follows: the vertices of Q(V) are the elements of V, and {O,V} is an edge of Q ( V ) if and only if no other W E Vagrees with U in all the positions in which V does. If Vrepresents the set of keys for