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

《山东大学学报(理学版)》 ›› 2020, Vol. 55 ›› Issue (9): 36-41.doi: 10.6040/j.issn.1671-9352.0.2019.610

• • 上一篇    下一篇

无相交三角形平面图的邻点可区别边染色

刘卓雅,徐常青*   

  1. 河北工业大学理学院, 天津 300401
  • 发布日期:2020-09-17
  • 作者简介:刘卓雅(1995— ), 女, 硕士研究生, 研究方向为图论. E-mail:liuzhuoya_dh@163.com*通信作者简介: 徐常青(1970— ), 女, 教授, 硕士生导师, 研究方向为图论. E-mail:chqxu@hebut.edu.cn
  • 基金资助:
    国家自然科学基金资助项目(11671232)

Adjacent vertex distinguishing edge coloring of planar graphs without intersecting triangles

LIU Zhuo-ya, XU Chang-qing*   

  1. School of Science, Hebei University of Technology, Tianjin 300401, China
  • Published:2020-09-17

PDF (PC)

826

摘要： 图G的k-邻点可区别边染色是指G的一个正常k-边染色满足对任意相邻顶点u和v,与u关联的边所染颜色集合和与v关联的边所染颜色集合不同。使G有k-邻点可区别边染色的k的最小值称为G的邻点可区别边色数,记作χ'a(G)。通过运用权转移方法研究了无相交三角形平面图的邻点可区别边色数,证明了若图G为无相交三角形平面图,则χ'a(G)≤max{Δ(G)+2,10}。

关键词: 平面图, 邻点可区别边染色, 邻点可区别边色数

Abstract: A k-adjacent vertex distinguishing edge coloring of a graph G is a proper k-edge coloring of G such that for any two adjacent vertices u and v, the color set of edges incident with u is different from the color set of edges incident with v. The least k for a k-adjacent vertex distinguishing edge coloring of G is the adjacent vertex distinguishing chromatic number, denoted by χ'a(G). By using the discharging method, we study the adjacent vertex distinguishing chromatic number of a planar graph without intersecting triangles, and get the conclusion: if G is a planar graph without intersecting triangles, then χ'a(G)≤max{Δ(G)+2,10}.

Key words: planar graph, adjacent vertex distinguishing edge coloring, adjacent vertex distinguishing chromatic number

中图分类号: 

  • O157.5
[1] ZHANG Zhongfu, LIU Linzhong, WANG Jianfang. Adjacent strong edge coloring of graphs[J]. Applied Mathematics Letters, 2002, 15(5):623-626.
[2] HOR(ˇoverN)ÁK M, HUANG Danjun, WANG Weifan. On neighbor-distinguishing index of planar graphs[J]. Journal of Graph Theory, 2014, 76(4):262-278.
[3] ZHU Junlei, BU Yuehua, DAI Yun. Upper bounds for adjacent vertex-distinguishing edge coloring[J]. Journal of Combinatorial Optimization, 2018, 35:454-462.
[4] BONAMY M, BOUSQUET N, HOCQUARD H. Adjacent vertex-distinguishing edge coloring of graphs[C] // The Seventh European Conference on Combinatorics, Graph Theory and Applications, 2013, 16:313-318.
[5] WANG Weifan, HUANG Danjun. A characterization on the adjacent vertex distinguishing index of planar graphs with large maximum degree[J]. SIAM Journal on Discrete Mathematics, 2015, 29(4):2412-2431.
[6] HUANG Danjun,MIAO Zhengke,WANG Weifan. Adjacent vertex distinguishing indices of planar graphs without 3-cycles[J]. Discrete Mathematics, 2015, 338(3):139-148.
[7] 严丞超,黄丹君,王维凡. 围长至少为 4 的可平面图的邻点可区别边染色[J]. 数学研究,2012,45(4):331-341. YAN Chengchao, HUANG Danjun, WANG Weifan. Adjacent vertex distinguishing edge-colorings of planar graphs with girth at least four[J]. Journal of Mathematical Study, 2012, 45(4):331-341.
[1] 李锦,徐常青. 不含相交三角形IC-可平面图的邻点可区别边染色[J]. 《山东大学学报(理学版)》, 2023, 58(12): 134-139.
[2] 谭香. 一类最大度为6的平面图的全染色[J]. 《山东大学学报(理学版)》, 2021, 56(11): 71-75.
[3] 陈宏宇,钟斌. 不含相交5-圈的平面图的线性2-荫度[J]. 《山东大学学报(理学版)》, 2020, 55(7): 38-45.
[4] 刘佳,孙磊. 不含4-圈或弦6-圈的平面图是(3,0,0)-可染的[J]. 《山东大学学报(理学版)》, 2018, 53(12): 31-40.
[5] 房启明,张莉. 无4-圈和5-圈的平面图的k-frugal列表染色[J]. 山东大学学报（理学版）, 2018, 53(10): 35-41.
[6] 王晓丽,王慧娟,刘彬. 最大度为7的平面图全染色[J]. 山东大学学报（理学版）, 2017, 52(8): 100-106.
[7] 王晔,孙磊. 不含3圈和4圈的1-平面图是5-可染的[J]. 山东大学学报（理学版）, 2017, 52(4): 34-39.
[8] 陈宏宇,张丽. 4-圈不共点的平面图的线性2-荫度[J]. 山东大学学报（理学版）, 2017, 52(12): 36-41.
[9] 谭香. 不含6-圈和相邻5-圈的平面图的全染色[J]. 山东大学学报（理学版）, 2016, 51(4): 72-78.
[10] 朱海洋,顾 毓,吕新忠. 平面图的平方染色数的一个新上界[J]. 山东大学学报（理学版）, 2016, 51(2): 94-101.
[11] 孟宪勇, 郭建华, 苏本堂. 3-正则Halin图的完备染色[J]. 山东大学学报（理学版）, 2015, 50(12): 127-129.
[12] 孟献青. 一类平面图的强边染色[J]. 山东大学学报（理学版）, 2015, 50(08): 10-13.
[13] 何雪, 田双亮. 若干图的倍图的邻点可区别边(全)染色[J]. 山东大学学报（理学版）, 2015, 50(04): 63-66.
[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
本系统由北京玛格泰克科技发展有限公司设计开发