您的位置：山东大学 -> 科技期刊社 -> 《山东大学学报（理学版）》

山东大学学报（理学版） ›› 2016, Vol. 51 ›› Issue (2): 94-101.doi: 10.6040/j.issn.1671-9352.0.2014.594

• • 上一篇    下一篇

平面图的平方染色数的一个新上界

朱海洋1,顾 毓1,吕新忠2   

  1. 1. 空军勤务学院飞行保障指挥系, 江苏 徐州 221000;2.浙江师范大学数理与信息工程学院, 浙江 金华 321004
  • 收稿日期:2014-12-31 出版日期:2016-02-16 发布日期:2016-03-11
  • 作者简介:朱海洋(1979— ),男,讲师,研究方向为图论与军事运筹学. E-mail:tulunzhuhaiyang7@126.com
  • 基金资助:
    国家自然科学基金资助项目(61170302)

New upper bound on the chromatic number of the square of a planar graph

ZHU Hai-yang1, GU Yu1, LÜ Xin-zhong2   

  1. 1. Department of Flight Support Command, Air Force Logistics College, Xuzhou 221000, Jiangsu, China;
    2. College of Mathematics, Physics and Information Engineering, Zhejiang Normal University, Jinhua 321004, Zhejiang, China
  • Received:2014-12-31 Online:2016-02-16 Published:2016-03-11

PDF (PC)

1415

摘要： 令V(G)、E(G)、Δ(G)和χ(G)分别为G的顶点集、边集、最大度和色数。图G的平方图,记为G2,指的是一个图满足条件:V(G2)=V(G),并且uv∈E(G2)当且仅当1≤dG(u,v)≤2。证明了若G是Δ(G)≤6且围长g(G)≥5的平面图,则χ(G2)≤Δ(G)+8。

关键词: 平面图, 染色, 围长, 平方图

Abstract: Let V(G), E(G), Δ(G) and χ(G) denote the vertex set, the edge set, the maximum degree and the chromatic number of a graph G, respectively. The square G2 of a graph G is defined such that V(G2)=V(G), and uv∈E(G2)if and only if 1≤dG(u,v)≤2. It is proved that χ(G2)≤Δ(G)+8 if G is a planar graph with Δ(G)≤6 and girth g(G)≥5.

Key words: planar graph, girth, coloring, squares

中图分类号: 

  • O157.5
[1] 徐俊明. 图论及其应用[M]. 2版. 合肥: 中国科学技术大学出版社, 2005. XU Junming. Graph theory and its applications[M]. 2nd ed. Hefei: China University of Science and Technology Press, 2005.
[2] WEGNER G. Graphs with given diameter and coloring problem[R]. Dortmund, Germany:Technical Report, University of Dortmund, 1977.
[3] HEUVEL J V, McGUINESS S. Coloring of the square of a planar graph[J]. J Graph Theory, 2003, 42:110-124.
[4] MOLLY M, SALAVATIPOUR M R. A bound on the chromatic number of the square of a planar graph[J]. J Combinatorial Theory: B, 2005, 94:189-213.
[5] WANG Weifan, CAI L Z. Labeling planar graphs without 4-cycles with a conditionon distance two[J]. J Discrete Applied Mathematics, 2008, 156:2241-2249.
[6] ZHU Haiyang, HOU Lifeng, CHEN Wei, et al. The L(p; q)-labelling of planar graphs without 4-cycles[J]. Discrete Applied Mathematics, 2014, 162:355-363.
[7] BORODIN O V, IVANOVA A O. 2-distance Δ+2-coloring of planar graphs with girth six and Δ(G)≥18[J]. Discrete Mathematics, 2009, 309:6496-6502.
[8] WANG Weifan, LIH K W. Labeling planar graphs with conditions on girth and distance two[J]. SIAM J Discrete Mathematics, 2003, 17(2):264-275.
[9] CHARPENTIER C, MONTASSIER M, RASPAUD A. L(p,q)-labeling of sparse graphs[J]. Journal of Combinatorial Optimization, 2013, 25(4):646-660.
[1] 吴弦禧,黄丹君. mad(G)≤(13)/4的图的均匀染色[J]. 《山东大学学报(理学版)》, 2025, 60(2): 41-50.
[2] 郭亚勤,陈祥恩. 完全二部图K1,n、K2,n、K3,n的点被多重集可区别的E-全染色[J]. 《山东大学学报(理学版)》, 2025, 60(2): 24-33.
[3] 田双亮,陈萍. 路的半强积与强积的距离染色[J]. 《山东大学学报(理学版)》, 2025, 60(12): 167-172.
[4] 白羽,强会英,何静. 联图Cm∨Cn的邻和可区别边染色[J]. 《山东大学学报(理学版)》, 2025, 60(12): 161-166.
[5] 胡开洋,黄明芳,马宝林. 完全二部图K12, n(12≤n≤88)的点可区别E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 36-43, 70.
[6] 陈宏宇. 树宽较小的图的线性荫度[J]. 《山东大学学报(理学版)》, 2024, 59(6): 25-28, 35.
[7] 王勇军,陈祥恩. 完全三部图的点被多重集可区别的一般全染色[J]. 《山东大学学报(理学版)》, 2024, 59(6): 29-35.
[8] 曹静,陈祥恩. 轮与扇的点被多重集可区别的E-全染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 38-46.
[9] 袁佳鑫,黄明芳. 不含K1, 3+图的强边染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 53-58.
[10] 史雅馨,刘凤霞,蔡华. Wn□Pm的r-hued染色[J]. 《山东大学学报(理学版)》, 2024, 59(2): 59-64.
[11] 雷飞,文飞,李泽鹏,李沐春. 图的字典积的点可约边染色[J]. 《山东大学学报(理学版)》, 2024, 59(10): 107-114.
[12] 朱利娜,李敬文,孙帅. 几类联图的L(2, 1)-边染色算法研究[J]. 《山东大学学报(理学版)》, 2023, 58(8): 63-72.
[13] 常景智,杨超,姚兵. 关于图的邻和可区别全染色的新方法[J]. 《山东大学学报(理学版)》, 2023, 58(6): 35-39.
[14] 李锦,徐常青. 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2023, 58(12): 134-139.
[15] 杨腾飞,徐常青. 3-退化图的全染色[J]. 《山东大学学报(理学版)》, 2022, 57(6): 61-63.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发