✦ LIBER ✦

Choosability of planar graphs

✍ Scribed by Margit Voigt

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 175 KB
Volume: 150
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(95)00216-j

No coin nor oath required. For personal study only.

✦ Synopsis

A graph G = G(EE) with lists L(v), associated with its vertices v E V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with IL(v)l = k Vv E V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (IL(v)] = k Vv E V(G)), every vertex v and every colour f E L(v). We prove the equivalence of the well-known conjecture of Erd6s et al. (1979): "Every planar graph is 5-choosable" with the following conjecture: "Every planar graph is free 5-choosable".

📜 SIMILAR VOLUMES

The complexity of planar graph choosabil

The complexity of planar graph choosability

✍ Shai Gutner 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 553 KB

Every Planar Graph Is 5-Choosable

✍ C. Thomassen 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 56 KB

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.

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

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

Choosability, Edge Choosability, and Tot

Choosability, Edge Choosability, and Total Choosability of Outerplane Graphs

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

Let χ l (G), χ l (G), χ l (G), and (G) denote, respectively, the list chromatic number, the list chromatic index, the list total chromatic number, and the maximum degree of a non-trivial connected outerplane graph G. We prove the following results. ( 1 and only if G is an odd cycle. This proves the

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