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

Discussiones Mathematicae Graph Theory (2006)

- Volume: 26, Issue: 1, page 91-101
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topYongqiang 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 -

## References

top- [1] N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull. of the ICA 25 (1999) 79-87. Zbl0916.05026
- [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. Zbl0978.05029
- [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. Zbl0941.05027
- [5] R. Skrekovski, List improper colorings of planar graphs, Comb. Prob. Comp. 8 (1999) 293-299, doi: 10.1017/S0963548399003752. Zbl0940.05031
- [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. Zbl0940.05027
- [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. Zbl0822.05029
- [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. Zbl0843.05034

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.