华东师范大学学报(自然科学版)

• 数学 • 上一篇    下一篇

平面图的3-hued 染色

齐林明, 李金波, 李卫奇   

  1. 1. 湖州职业技术学院~~旅游与公共管理学院, 浙江 湖州 313000;
    2. 中国矿业大学 理学院，江苏 徐州 221000
  • 收稿日期:2016-01-26 出版日期:2017-01-25 发布日期:2017-01-13
  • 通讯作者: 李金波, 男, 副教授, 研究方向为图论、运筹学. E-mail: lijibo@cumt.edu.cn.
  • 基金资助:

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

3-hued coloring of planar graphs

QI Lin-ming[1], LI Jin-bo[2], LI Wei-qi[2]   

  1. 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:2016-01-26 Online:2017-01-25 Published:2017-01-13

RichHTML

12

PDF

840

摘要：

对于整数 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.

关键词: 平面图, 极小反例, 勒贝格公式

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