The use of Euler's formula in (3,1)*-list coloring

Yongqiang Zhao, and Wenjie He. "The use of Euler's formula in (3,1)*-list coloring." Discussiones Mathematicae Graph Theory 26.1 (2006): 91-101. <http://eudml.org/doc/270497>.

@article{YongqiangZhao2006,
abstract = {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.},
author = {Yongqiang Zhao, Wenjie He},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {list improper coloring; (L,d)*-coloring; (m,d)*-choosable; Euler's formula; list improper colouring; -colouring; -choosable},
language = {eng},
number = {1},
pages = {91-101},
title = {The use of Euler's formula in (3,1)*-list coloring},
url = {http://eudml.org/doc/270497},
volume = {26},
year = {2006},
}

TY - JOUR
AU - Yongqiang Zhao
AU - Wenjie He
TI - The use of Euler's formula in (3,1)*-list coloring
JO - Discussiones Mathematicae Graph Theory
PY - 2006
VL - 26
IS - 1
SP - 91
EP - 101
AB - 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.
LA - eng
KW - list improper coloring; (L,d)*-coloring; (m,d)*-choosable; Euler's formula; list improper colouring; -colouring; -choosable
UR - http://eudml.org/doc/270497
ER -