HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information

# Improper choosability of graphs and maximum average degree

1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : Improper choosability of planar graphs has been widely studied. In particular, Skrekovski investigated the smallest integer $g_k$ such that every planar graph of girth at least $g_k$ is $k$-improper $2$-choosable. He proved that $6\leq g_1\leq 9$; $5\leq g_2\leq 7$; $5\leq g_3\leq 6$ and $\forall k\geq 4, g_k=5$. In this paper, 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 for $l\geq 2$ then $M(k,l)\geq l+\frac{lk}{l+k}$. As a corollary, we deduce that $g_1\leq 8$ and $g_2\leq 6$. We also provide an upper bound for $M(k,l)$. This implies that for any fixed $l$, $M(k,l)\xrightarrow[k\rightarrow\infty]{}2l$.
Keywords :
Document type :
Reports
Domain :

Cited literature [1 references]

https://hal.inria.fr/inria-00071425
Contributor : Rapport de Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 5:29:10 PM
Last modification on : Friday, February 4, 2022 - 3:11:28 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:12:44 PM

### Identifiers

• HAL Id : inria-00071425, version 1

### Citation

Frédéric Havet, Jean-Sébastien Sereni. Improper choosability of graphs and maximum average degree. RR-5164, INRIA. 2004. ⟨inria-00071425⟩

Record views