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

山东大学学报（理学版） ›› 2015, Vol. 50 ›› Issue (08): 10-13.doi: 10.6040/j.issn.1671-9352.0.2015.165

• 论文 • 上一篇    下一篇

一类平面图的强边染色

孟献青1,2   

  1. 1. 山西大同大学数学与计算机科学学院, 山西 大同 037009;
    2. 山东大学数学学院, 山东 济南 250100
  • 收稿日期:2015-04-17 出版日期:2015-08-20 发布日期:2015-07-31
  • 作者简介:孟献青(1979- ),女,硕士,讲师,研究方向为图论及其应用. E-mail:mxq1979@163.com
  • 基金资助:
    山西省青年科技研究基金项目(2013021001-1);山西省高等学校科技研究开发项目(20121015)

Strong edge coloring of a class of planar graphs

MENG Xian-qing1,2   

  1. 1. School of Mathematics and Computer Sciences, Shanxi Datong University, Datong 037009, Shanxi, China;
    2. School of Mathematics, Shandong University, Jinan 250100, Shandong, China
  • Received:2015-04-17 Online:2015-08-20 Published:2015-07-31

PDF (PC)

652

摘要： 图G的强边染色是指对图G的边进行染色,使得距离不超过2的任意两条边染不同的颜色. 任何一个平面图都可用4Δ+4种颜色进行强边染色. 证明了当平面图没有k-圈(4≤k≤10)且3-圈不相交时(即每个顶点至多关联一个3-圈), 必定存在一个3Δ+1种颜色的强边染色.

关键词: 平面图, 强边染色, 强边色数, 圈

Abstract: A strong edge coloring of a graph G is an assignment of colors to the edges of the graph such that any two edges at distance at most 2 receive distinct colors. It is known that every planar graph has a strong edge-coloring with at most 4Δ+4 colors. It is proved that planar graph G has a strong edge-coloring with at most 3Δ+1 colors if G has no k-cycles with 4≤k≤10 and no intersecting 3-cycles (that is, every vertex is incident with at most one cycle of length 3).

Key words: planar, cycle, srtong chromaic index, strong edge coloring

中图分类号: 

  • O157.5
[1] BONDY J A, MURTY U S R. Graph theory with applications[M]. London: Macmillan, 1976.
[2] ANDERSEN L D. The strong chromatic index of a cubic graph is at most 10[J]. Discrete Mathematics, 1992, 108:231-252.
[3] HORÁK P, HE Qing, TROTTER W T. Induced matchings in cubic graphs[J]. Graph Theory, 1993, 17(2):151-160.
[4] CRANSTON D. Strong edge-coloring graphs with maximum degree 4 using 22 colors[J]. Discrete Mathematics, 2006, 306:2772-2778.
[5] FAUDREE R J, GYSRFAS A, SCHELP R H, et al. The strong chromatic index of graphs[J]. Ars Combin, 1990, 29B:205-211.
[6] BORODIN 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.
[7] MONTASSIER 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.
[8] HUDÁK D, LU?AR B, SOTÁK R, et al. Strong edge-coloring of planar graphs[J]. Discrete Mathematics, 2014, 324:41-49.
[9] BENSMAIL J, HARUTYUNYAN A, HOCQUARD H, et al. Strong edge-coloring of sparse planar graphs[J]. Discrete Applied Mathematics, 2014, 179:229-234.
[1] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[2] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[3] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
[4] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[5] 何玉萍,王治文,陈祥恩. mC8的点可区别全染色[J]. 山东大学学报（理学版）, 2017, 52(10): 24-30.
[6] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[7] 白丹,左连翠. 立方圈的(d,1)-全标号[J]. 山东大学学报（理学版）, 2016, 51(4): 59-64.
[8] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101.
[9] 孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报（理学版）, 2015, 50(12): 127-129.
[10] 薛丽霞, 李志慧, 谢佳丽. 对3条超边的超圈存取结构最优信息率的一点注记[J]. 山东大学学报（理学版）, 2015, 50(11): 60-66.
[11] 王珊珊, 齐恩凤. k-连通图中最长圈上可收缩边的数目[J]. 山东大学学报（理学版）, 2015, 50(10): 27-31.
[12] 张绍华, 颜谨, 李硕. 图中相互独立的4-圈和8-圈[J]. 山东大学学报（理学版）, 2015, 50(02): 1-4.
[13] 杨陈, 马海成. 两类特殊三圈图的正负惯性指数和零度[J]. 山东大学学报（理学版）, 2015, 50(02): 32-37.
[14] 马刚. 围长不小于11且最大度为3的平面图的#br# 无圈列表边染色[J]. 山东大学学报（理学版）, 2014, 49(2): 18-23.
[15] 陈宏宇1, 张丽2. 不含弦5-圈和弦6-圈的平面图的线性2荫度[J]. 山东大学学报（理学版）, 2014, 49(06): 26-30.
Viewed
Full text


Abstract

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