zbMATH — the first resource for mathematics

Improper choosability of graphs and maximum average degree. (English) Zbl 1104.05026
A graph \(G= (V,E)\) is called \(k\)-improper \(l\)-choosable – or \((l,k)^*\)-choosable – if for any list-assignment \(L\) with \(|L(v)|\geq l\) for each vertex \(v\) there is a colouring of \(V\) according to the given lists such that no vertex \(v\) has more than \(k\) neighbours having the same colour as \(v\). The maximum average degree of \(G\) is the maximum of the average degree of each of its subgraphs. This paper studies the greatest real \(M(k,l)\) such that every graph of maximum average degree less than \(M(k,l)\) is \((l, k)^*\)-choosable. It is shown that \(M(k,l)\geq l+{lk\over l+k}\), yielding as a corollary an improvement of results of R. Škrekovski [Discrete Math. 214, No. 1–3, 221–233 (2000; Zbl 0940.05027)] on the smallest integer \(g_k\) such that every planar graph of girth at least \(k\) is \((2,k)^*\)-choosable: \(g_1\leq 8\) and \(g_2\leq 6\). Also an upper bound for \(M(k,l)\) is given, implying that \(\lim_{k\to\infty}= 2l\) for any fixed \(l\). Finally, some results on improper choosability for graphs of higher genus are given.

05C15 Coloring of graphs and hypergraphs
Full Text: DOI
[1] Appel, Illinois J Math 21 pp 429– (1977)
[2] Appel, Illinois J Math 21 pp 491– (1977)
[3] Eaton, Bull Inst Combin Appl 25 pp 79– (1999)
[4] Grötzsch, Math-nat 8 pp 109– (1959)
[5] Miao, Discrete Math 269 pp 311– (2003)
[6] Alon, Graphs Combin 18 pp 53– (2002)
[7] Škrekovski, Comb Prob Comp 8 pp 293– (1999)
[8] Škrekovski, Comb Prob Comp 8 pp 493– (1999)
[9] Škrekovski, Discrete Math 214 pp 221– (2000)
[10] Thomassen, J Comb Theory B 62 pp 180– (1994)
[11] Thomassen, J Comb Theory B 64 pp 101– (1995)
[12] Thomassen, J Comb Theory B 88 pp 189– (2003)
[13] Voigt, Discrete Math 120 pp 215– (1993)
[14] Voigt, Discrete Math 146 pp 325– (1995)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.