Premium
Improper choosability of graphs and maximum average degree
Author(s) -
Havet Frédéric,
Sereni JeanSébastien
Publication year - 2006
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20155
Subject(s) - combinatorics , mathematics , planar graph , graph , corollary , degree (music) , girth (graph theory) , integer (computer science) , upper and lower bounds , discrete mathematics , physics , computer science , mathematical analysis , acoustics , programming language
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