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/}
}
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/