平面图的3-hued染色

基金项目:

湖州职业技术学院校级规划课题 2016JC10

3-hued coloring of planar graphs

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

摘要: 对于整数k,r＞0,图G的(k,r)-染色是一个正常k染色,使得对于每一个度数为d(v)的点v,v的邻点至少表现min{d(v),r}种颜色, 这样的染色,称之为r-hued染色, 图G的r-hued染色数, 记作$\chi_{r}(G)$,是使图G存在(k,r)染色的最小的k值. 在这篇文章中, 证明了,对于一般平面图G, $\chi_{3}(G)\leq 12$.
- 平面图 /
- 极小反例 /
- 勒贝格公式
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

图 1 定理2.1中的情形1.1-1.3

Fig. 1 Configurations 1.1-1.3 in Theorem 2.1

下载: 全尺寸图片幻灯片

图 2 定理2.1中的情形2.1-3.1

Fig. 2 Configurations 2.1-3.1 in Theorem 2.1

下载: 全尺寸图片幻灯片

图 3 定理2.1中的情形4.1-4.2

Fig. 3 Configurations 4.1-4.2 in Theorem 2.1

下载: 全尺寸图片幻灯片

[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