华东师范大学学报（自然科学版） >

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

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

数学

平面图的3-hued 染色

  • 齐林明 ,
  • 李金波 ,
  • 李卫奇
展开
  • 1. 湖州职业技术学院~~旅游与公共管理学院, 浙江 湖州 313000;
    2. 中国矿业大学 理学院，江苏 徐州 221000

收稿日期: 2016-01-26

  网络出版日期: 2017-01-13

基金资助

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

收起

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

摘要

对于整数 k,r>0 , 图 G 的 (k,r) 染色是一个正常 k 染色, 使得对于每一个度数为 d(v) 的点 v ,  v 的邻点至少表现 min{d(v),r}种颜色, 这样的染色, 称之为 r-hued 染色, 图 G 的 r-hued 染色数, 记作 χr(G), 是使图 G 存在 (k,r) 染色的最小的 k 值. 在这篇文章中, 证明了, 对于一般平面图 G, χ3(G)≤12.

关键词： 平面图; 极小反例; 勒贝格公式

本文引用格式

齐林明 , 李金波 , 李卫奇 . 平面图的3-hued 染色[J]. 华东师范大学学报（自然科学版）, 2017 , 2017(1) : 32 -37 . DOI: 10.3969/j.issn.1000-5641.2017.01.005

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

参考文献

[ 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
文章导航

/

〈 〉