✦ LIBER ✦

Improper choosability of graphs and maximum average degree

✍ Scribed by Frédéric Havet; Jean-Sébastien Sereni

Publisher: John Wiley and Sons
Year: 2006
Tongue: English
Weight: 174 KB
Volume: 52
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.20155

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Improper choosability of planar graphs has been widely studied. In particular, Škrekovski investigated the smallest integer g~k~ such that every planar graph of girth at least g~k~ is k‐improper 2‐choosable. He proved [9] that 6 ≤ g~1~ ≤ 9; 5 ≤ g~2~ ≤ 7; 5 ≤ g~3~ ≤ 6; and ∀ k ≥ 4, g~k~ = 5. In this article, we study the greatest real M(k, l) such that every graph of maximum average degree less than M(k, l) is k‐improper l‐choosable. We prove that if l ≥ 2 then $M(k, l) \geq l + {l {\rm k} \over {l+k}}$. As a corollary, we deduce that g~1~ ≤ 8 and g~2~ ≤ 6, and we obtain new results for graphs of higher genus. We also provide an upper bound for M(k, l). This implies that for any fixed l, $M(k,l) \displaystyle\mathop{\longrightarrow}_{k \rightarrow \infty}{2l}$. © 2006 Wiley Periodicals, Inc. J Graph Theory 52: 181–199, 2006

📜 SIMILAR VOLUMES

(d,1)-total labeling of graphs with a gi

(d,1)-total labeling of graphs with a given maximum average degree

✍ Mickaël Montassier; André Raspaud 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 166 KB 👁 1 views

## Abstract The (__d__,1)‐total number $\lambda \_{d}^{T}(G)$ of a graph __G__ is the width of the smallest range of integers that suffices to label the vertices and the edges of __G__ so that no two adjacent vertices have the same color, no two incident edges have the same color, and the distance

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.

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

Maximum degree in graphs of diameter 2

✍ Paul Erdös; Siemion Fajtlowicz; Alan J. Hoffman 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 163 KB

Weight choosability of graphs

✍ Tomasz Bartnicki; Jarosław Grytczuk; Stanisław Niwczyk 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 155 KB

## Abstract Suppose the edges of a graph __G__ are assigned 3‐element lists of real weights. Is it possible to choose a weight for each edge from its list so that the sums of weights around adjacent vertices were different? We prove that the answer is positive for several classes of graphs, includi

Circular choosability of graphs

✍ Xuding Zhu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 105 KB

This paper discusses the circular version of list coloring of graphs. We give two definitions of the circular list chromatic number (or circular choosability) c;l ðGÞ of a graph G and prove that they are equivalent. Then we prove that for any graph G, c;l ðGÞ ! l ðGÞ À 1. Examples are given to show