✦ LIBER ✦

On list-coloring outerplanar graphs

✍ Scribed by Joan P. Hutchinson

Publisher: John Wiley and Sons
Year: 2008
Tongue: English
Weight: 162 KB
Volume: 59
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20326

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

We prove that a 2‐connected, outerplanar bipartite graph (respectively, outerplanar near‐triangulation) with a list of colors L (v ) for each vertex v such that $|L(v)|\geq\min{{\deg}(v),4}$ (resp., $|L(v)|\geq{\min}{{\deg}(v),5}$) can be L‐list‐colored (except when the graph is K~3~ with identical 2‐lists). These results are best possible for each condition in the hypotheses and bounds. © 2008 Wiley Periodicals, Inc. J Graph Theory 59: 59–74, 2008

📜 SIMILAR VOLUMES

A decomposition for total-coloring parti

A decomposition for total-coloring partial-grids and list-total-coloring outerplanar graphs

✍ Raphael C. S. Machado; Celina M. H. de Figueiredo 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 285 KB

Adapted list coloring of planar graphs

✍ Louis Esperet; Mickaël Montassier; Xuding Zhu 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 1 views

## Abstract Given an edge coloring __F__ of a graph __G__, a vertex coloring of __G__ is __adapted to F__ if no color appears at the same time on an edge and on its two endpoints. If for some integer __k__, a graph __G__ is such that given any list assignment __L__ to the vertices of __G__, with |_

Acyclic list 7-coloring of planar graphs

✍ O. V. Borodin; D. G. Fon-Der Flaass; A. V. Kostochka; A. Raspaud; E. Sopena 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 83 KB 👁 1 views

Augmenting Outerplanar Graphs

✍ Goos Kant 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 269 KB

In this paper, we show that for outerplanar graphs G the problem of augmenting G by adding a minimum number of edges such that the augmented graph GЈ is planar and bridge-connected, biconnected, or triconnected can be solved in linear time and space. It is also shown that augmenting a biconnected ou

Oriented list colorings of graphs

✍ Zs. Tuza; M. Voigt 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 159 KB 👁 1 views

A 2-assignment on a graph G (V,E) is a collection of pairs Lv of allowed colors speci®ed for all vertices v PV. The graph G (with at least one edge) is said to have oriented choice number 2 if it admits an orientation which satis®es the following property: For every 2-assignment there exists a choic

3-List-Coloring Planar Graphs of Girth 5

✍ C. Thomassen 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 269 KB

We prove that every planar graph of girth at least 5 is 3-choosable. It is even possible to precolor any 5-cycle in the graph. This extension implies Grötzsch's theorem that every planar graph of girth at least 4 is 3-colorable. If 1995 Academic Press, Inc.