Skip to Main content Skip to Navigation

Improper choosability of graphs and maximum average degree

Frédéric Havet 1 Jean-Sébastien Sereni
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$.
Document type :
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 5:29:10 PM
Last modification on : Monday, October 12, 2020 - 10:30:21 AM
Long-term archiving on: : Sunday, April 4, 2010 - 10:12:44 PM


  • HAL Id : inria-00071425, version 1



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



Record views


Files downloads