不含短圈平面图的强边染色

Strong Edge Coloring of Planar Graphs without Short Cycles

下载PDF

导出

摘要图G的强边染色是在正常边染色的基础上,要求距离不超过2的任意两条边染不同的颜色。强边染色所用颜色的最小整数称为图G的强边色数。文章首先给出极小反例的构型,然后通过权转移方法,证明了3-圈、4-圈互不相交且没有k-圈(5≤k≤10)的平面图的强边色数至多是3Δ(G)+1.

作者张恒

机构地区浙江师范大学数理与信息工程学院

出处《应用数学进展》 2018年第6期661-666,共6页 Advances in Applied Mathematics

关键词平面图强边染色强边色数圈 Planar Graphs Strong Edge Coloring Strong Edge Chromatic Number Cycle

参考文献2

1BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan, 1976.
2ANDERSEN L D. The strong chromatic index of a cubic graph is at most 10[J]. Discrete Mathematics, 1992, 108:231-252.
3HORáK P, HE Qing, TROTTER W T. Induced matchings in cubic graphs[J]. Graph Theory, 1993, 17(2):151-160.
4CRANSTON D. Strong edge-coloring graphs with maximum degree 4 using 22 colors[J]. Discrete Mathematics, 2006, 306:2772-2778.
5FAUDREE R J, GYSRFAS A, SCHELP R H, et al. The strong chromatic index of graphs[J]. Ars Combin, 1990, 29B:205-211.
6BORODIN O V, IVANOVA A O. Precise upper bound for the strong edge chromatic number of sparse planar graphs[J]. Discuss Math Graph Theory, 2013, 33:759-770.
7MONTASSIER M, PêCHER A, RASPAUD A. Strong chromatic index of planar graphs with large girth[J]. Graph Theory and Applications, CRM Series, 2013, 16:265-270.
8HUDáK D, LU?AR B, SOTáK R, et al. Strong edge-coloring of planar graphs[J]. Discrete Mathematics, 2014, 324:41-49.
9BENSMAIL J, HARUTYUNYAN A, HOCQUARD H, et al. Strong edge-coloring of sparse planar graphs[J]. Discrete Applied Mathematics, 2014, 179:229-234.
10Andersen L D. The strong chromatic index of a cubic graph is at most 10[J]. Discrete Mathematics, 1992, 108: 231-252.

1Fei YAN,Sihao JIAO,Abdullah M. ILIYASU,Zhengang JIANG.Chromatic framework for quantum movies and applications in creating montages[J].Frontiers of Computer Science,2018,12(4):736-748. 被引量：1
2卜月华,王丽霞.最大度为5的简单图的2-距离列表染色[J].浙江师范大学学报（自然科学版）,2018,41(2):121-129. 被引量：1
3陈宏宇,张丽.4-圈不共点的平面图的线性2-荫度[J].山东大学学报（理学版）,2017,52(12):36-41.
4姚顺禹,马登举.麦比乌斯梯子C(2n,n)的强边色数[J].数学杂志,2018,38(3):497-501.
5帝斯曼集团计划将热固性材料引入3D打印产品[J].工程塑料应用,2018,46(5):129-129.
6滕佳昆,刘宇,丁明涛.基于RGB图像的刺槐季节变化监测适用指数研究[J].遥感技术与应用,2018,33(3):476-485. 被引量：8
7颜慧慧.平面图的在线4列表染色[J].运筹与模糊学,2018,8(2):39-44.
8巴西MK27工作室设计草覆盖平面屋顶住宅[J].中外建筑,2018,0(9):268-269.
9孟献青,宋慧敏.特殊平面图的强边染色（英文）[J].数学进展,2017,46(5):667-672.

应用数学进展

2018年第6期

内容加载中请稍等...