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

Yongqiang Zhao; Wenjie He

Discussiones Mathematicae Graph Theory (2006)

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

Abstract

top
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 [ ( 5 i - 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.

How to cite

top

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 -

References

top
  1. [1] N. Eaton and T. Hull, Defective list colorings of planar graphs, Bull. of the ICA 25 (1999) 79-87. Zbl0916.05026
  2. [2] P. Erdös, A.L. Rubin and H. Taylor, Choosability in graphs, Congr. Numer. 26 (1979) 125-157. 
  3. [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. [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. [5] R. Skrekovski, List improper colorings of planar graphs, Comb. Prob. Comp. 8 (1999) 293-299, doi: 10.1017/S0963548399003752. Zbl0940.05031
  6. [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. [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. [8] V.G. Vizing, Vertex coloring with given colors (in Russian), Diskret. Analiz. 29 (1976) 3-10. 
  9. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.