Geodesic
The use of Euler's formula in (3,1)*-list coloring
Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 1, pp. 91-101.

Voir la notice de l'article provenant de la source Library of Science

A graph G is called (k,d)*-choosable if, for every list assignment L satisfying |L(v)| = k for all v ∈ V(G), there is an L-coloring of G such that each vertex of G has at most d neighbors colored with the same color as itself. Ko-Wei Lih et al. used the way of discharging to prove that every planar graph without 4-cycles and i-cycles for some i ∈ 5,6,7 is (3,1)*-choosable. In this paper, we show that if G is 2-connected, we may just use Euler's formula and the graph's structural properties to prove these results. Furthermore, for 2-connected planar graph G, we use the same way to prove that, if G has no 4-cycles, and the number of 5-cycles contained in G is at most 11 + ⎣∑_i≥5 [(5i-24)/4] |V_i|⎦, then G is (3,1)*-choosable; if G has no 5-cycles, and any planar embedding of G does not contain any adjacent 3-faces and adjacent 4-faces, then G is (3,1)*-choosable.
Keywords: list improper coloring, (L,d)*-coloring, (m,d)*-choosable, Euler's formula 
@article{DMGT_2006_26_1_a8,
     author = {Zhao, Yongqiang and He, Wenjie},
     title = {The use of {Euler's} formula in (3,1)*-list coloring},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {91--101},
     publisher = {mathdoc},
     volume = {26},
     number = {1},
     year = {2006},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a8/}
}
TY  - JOUR
AU  - Zhao, Yongqiang
AU  - He, Wenjie
TI  - The use of Euler's formula in (3,1)*-list coloring
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2006
SP  - 91
EP  - 101
VL  - 26
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a8/
LA  - en
ID  - DMGT_2006_26_1_a8
ER  - 
%0 Journal Article
%A Zhao, Yongqiang
%A He, Wenjie
%T The use of Euler's formula in (3,1)*-list coloring
%J Discussiones Mathematicae. Graph Theory
%D 2006
%P 91-101
%V 26
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a8/
%G en
%F DMGT_2006_26_1_a8
Zhao, Yongqiang; He, Wenjie. The use of Euler's formula in (3,1)*-list coloring. Discussiones Mathematicae. Graph Theory, Tome 26 (2006) no. 1, pp. 91-101. http://geodesic.mathdoc.fr/item/DMGT_2006_26_1_a8/

[1] N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull. of the ICA 25 (1999) 79-87.

[2] P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157.

[3] K. Lih, Z. Song, W. Wang and K. Zhang, A note on list improper coloring planar graphs, Appl. Math. Letters 14 (2001) 269-273, doi: 10.1016/S0893-9659(00)00147-6.

[4] R. Skrekovski, A grötzsch-type theorem for list colorings with impropriety one, Comb. Prob. Comp. 8 (1999) 493-507, doi: 10.1017/S096354839900396X.

[5] R. Skrekovski, List improper colorings of planar graphs, Comb. Prob. Comp. 8 (1999) 293-299, doi: 10.1017/S0963548399003752.

[6] R. Skrekovski, List improper colorings of planar graphs with prescribed girth, Discrete Math. 214 (2000) 221-233, doi: 10.1016/S0012-365X(99)00145-4.

[7] C. Thomassen, 3-list coloring planar graphs of girth 5, J. Combin. Theory (B) 64 (1995) 101-107, doi: 10.1006/jctb.1995.1027.

[8] V.G. Vizing, Vertex coloring with given colors (in Russian), Diskret. Analiz. 29 (1976) 3-10.

[9] M. Voigt, A not 3-choosable planar graph without 3-cycles, Discrete Math. 146 (1995) 325-328, doi: 10.1016/0012-365X(94)00180-9.