✦ LIBER ✦

The 4-Choosability of Plane Graphs without 4-Cycles

✍ Scribed by Peter Che Bor Lam; Baogang Xu; Jiazhuang Liu

Publisher: Elsevier Science
Year: 1999
Tongue: English
Weight: 179 KB
Volume: 76
Category: Article
ISSN: 0095-8956
DOI: 10.1006/jctb.1998.1893

No coin nor oath required. For personal study only.

✦ Synopsis

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-choosable.

📜 SIMILAR VOLUMES

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.

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

Graphs of degree 4 are 5-edge-choosable

✍ Juvan, Martin; Mohar, Bojan; ??krekovski, Riste 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 312 KB 👁 1 views

It is shown that every simple graph with maximal degree 4 is 5-edgechoosable.

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