Journal of East China Normal University(Natural Science) >

2017 , Vol. 2017 >Issue 1: 32 - 37

DOI: https://doi.org/10.3969/j.issn.1000-5641.2017.01.005

3-hued coloring of planar graphs

  • QI Lin-ming ,
  • LI Jin-bo ,
  • LI Wei-qi
Expand
  • 1. School of Tourism and Public Management, Huzhou Vocational and Technical College, Huzhou Zhejiang 313000, China;
    2. College of Sciences, China University of Mining and Technology, Xuzhou Jiangsu 221000, China

Received date: 2016-01-26

  Online published: 2017-01-13

Fold

Abstract

For a fixed integer k, r > 0, a (k, r)-coloring of a graph G is a proper k-coloring such that for any vertex v with degree d(v), the adjacent vertex of v is adjacent to at least min{d(v), r} different colors. Such coloring is also called as a r-hued coloring. The r-hued chromatic number of G, denoted by χr(G), is the smallest integer k such that G has a (k, r)-coloring. In this paper, we prove that if G is a planar graph, then χ3(G)≤12.

Key words： planar graphs; minimal counterexample; Lebesgue formula

Cite this article

QI Lin-ming , LI Jin-bo , LI Wei-qi . 3-hued coloring of planar graphs[J]. Journal of East China Normal University(Natural Science), 2017 , 2017(1) : 32 -37 . DOI: 10.3969/j.issn.1000-5641.2017.01.005

References

[ 1 ] BONDY J A, MURTY U S R. Graph Theory[M]. Berlin: Springer, 2008.
[ 2 ] SONG H M, LAI H J, WU J L. On r-hued coloring of planar graphs with grith at least 6[J]. Discrete Appl Math,2016, 198: 251-263.
[ 3 ] CHEN Y, FAN S H, LAI H J, et al. On dynamic coloring for planar graphs and graphs of higher genus[J].Discrete Appl Math, 2012, 160: 1064-1071.
[ 4 ] 林越. 图的条件着色的上界[D]. 广州: 暨南大学, 2008.
[ 5 ] APPEL K, HAKEN W, KOCK J. Every plane map is four colorable, Part I: Discharging[J]. Illinois J Math,1977, 21: 429-490.
[ 6 ] 丁超, 樊锁海, 赖宏建, 图的条件色数的上界[J].暨南大学学报(自然科学与医学版), 2008, 29(1): 35-38.

Options
Outlines

/

〈 〉