3-hued coloring of planar graphs

QI Lin-ming; LI Jin-bo; LI Wei-qi

doi:10.3969/j.issn.1000-5641.2017.01.005

Issue 1

Jan. 2017

Turn off MathJax

Article Contents

Article Navigation > Journal of East China Normal University (Natural Sciences) > 2017 > (1): 32-37

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

Citation:

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

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

Citation:

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

PDF( 293 KB)

3-hued coloring of planar graphs

doi: 10.3969/j.issn.1000-5641.2017.01.005

QI Lin-ming^1
,,
LI Jin-bo^{2
,
,},
LI Wei-qi²

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
Publish Date: 2017-01-25

Abstract

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 $\chi_{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 $\chi_{3}(G) \leq 12$.
- planar graphs,
- minimal counterexample,
- Lebesgue formula

FullText(HTML)

References(6)

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. doi: 10.1016/j.dam.2015.05.015
[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. doi: 10.1016/j.dam.2012.01.012
[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. http://www.cnki.com.cn/Article/CJFDTOTAL-JNDX200801011.htm