HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
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 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


  • 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