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

《山东大学学报(理学版)》 ›› 2024, Vol. 59 ›› Issue (2): 53-58.doi: 10.6040/j.issn.1671-9352.0.2022.557

•   • 上一篇    下一篇

不含K1, 3+图的强边染色

袁佳鑫(),黄明芳*()   

  1. 武汉理工大学理学院, 湖北 武汉 430070
  • 收稿日期:2022-10-31 出版日期:2024-02-20 发布日期:2024-02-20
  • 通讯作者: 黄明芳 E-mail:2461634998@qq.com;ds_hmf@126.com
  • 作者简介:袁佳鑫(1999—), 女, 硕士研究生, 研究方向为图论. E-mail: 2461634998@qq.com
  • 基金资助:
    国家自然科学基金资助项目(12261094)

Strong edge-coloring of graphs without K1, 3+

Jiaxin YUAN(),Mingfang HUANG*()   

  1. School of Science, Wuhan University of Technology, Wuhan 430070, Hubei, China
  • Received:2022-10-31 Online:2024-02-20 Published:2024-02-20
  • Contact: Mingfang HUANG E-mail:2461634998@qq.com;ds_hmf@126.com

RichHTML

0

PDF (PC)

84

摘要：

一个图G的强边染色是将颜色分配给所有的边, 使得每个颜色类的导出子图是一个匹配。在图G的强边染色中所需的最小颜色数称为图G的强边色数, 边e=uv的度记为d(e)=d(u)+d(v), 图G的边度记为d(G)=min{d(e)|e ∈ E(G)}。证明最大度为Δ且图的边度大于顶点数的不含K1, 3+图的强边色数至多是Δ2-Δ+1。

关键词: 强边染色, 强边色数, 边度

Abstract:

The strong edge-coloring of a graph G is to assign colors to all edges, so that the derived subgraphs of each color class are a matching. The minimum number of colors required in the strong edge-coloring of a graph G is called the strong chromatic index of the graph G, the degree of edge e=uv is recorded as d(e)=d(u)+d(v), the edge degree of G is recorded as d(G)=min{d(e)|e ∈ E(G)}. This paper proves that the strong chromatic index of the graph without K1, 3+ with the maximum degree Δ and edge degree of the graph greater than the number of vertices is at most Δ2-Δ+1.

Key words: strong edge-coloring, strong chromatic index, edge degree

中图分类号: 

  • O157

图1

图G中顶点v1、v2的邻点(除v1、v2外)划分为D1、D2、D3这3个顶点集"

1 FOUQUET J L , JOLIVET J L . Strong edge-colorings of graphs and applications to multi-k-gons[J]. Ars Combinatoria A, 1983, 16, 141- 150.
2 MOLLOY M , REED B . A bound on the strong chromatic index of a graph[J]. Journal of Combinatorial Theory: Series B, 1997, 69 (2): 103- 109.
doi: 10.1006/jctb.1997.1724
3 BRUHN H , JOOS F . A stronger bound for the strong chromatic index[J]. Combinatorics, Probability and Computing, 2018, 27 (1): 21- 43.
doi: 10.1017/S0963548317000244
4 HURLEY E, DE JOANNIS DE VERCLOS R, KANG R J. An improved procedure for colouring graphs of bounded local density[C]//Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA). New York: Society for Industrial and Applied Mathematics, 2021: 135-148.
5 ERDÖS P . Problems and results in combinatorial analysis and graph theory[J]. Discrete Mathematics, 1988, 72 (1/2/3): 81- 92.
6 HUDÁK D , LUŽAR B , SOTÁK R , et al. Strong edge-coloring of planar graphs[J]. Discrete Mathematics, 2014, 324, 41- 49.
doi: 10.1016/j.disc.2014.02.002
7 孟献青. 一类平面图的强边染色[J]. 山东大学学报(理学版), 2015, 50 (8): 10- 13.
MENG Xianqing . Strong edge coloring of a class of planar graphs[J]. Journal of Shandong University(Natural Science), 2015, 50 (8): 10- 13.
8 孟献青. 没有短圈的平面图的强边染色[J]. 南开大学学报(自然科学版), 2015, 48 (6): 1- 5.
MENG Xianqing . Strong edge coloring of planar graphs without short cycles[J]. Journal of Nankai University(Natural Science), 2015, 48 (6): 1- 5.
9 卜月华, 张恒. 平面图的强边染色[J]. 运筹学学报, 2022, 26 (2): 111- 127.
BU Yuehua , ZHANG Heng . Strong edge coloring of planar graphs[J]. Journal of Operational Research, 2022, 26 (2): 111- 127.
10 LIH K W , WANG W F , ZHU X D . Coloring the square of a K4-minor free graph[J]. Discrete Mathematics, 2003, 269 (1): 303- 309.
11 WANG Yiqiao , WANG Ping , WANG Weifan . Strong chromatic index of K4-minor free graphs[J]. Information Processing Letters, 2018, 129, 53- 56.
12 DȨBSKI M , JUNOSZA-SZANIAWSKI K , ŚLESZYŃSKA-NOWAK M . Strong chromatic index of K1, t-free graphs[J]. Discrete Applied Mathematics, 2020, 284, 53- 60.
13 DȨBSKI M , ŚLESZYŃSKA-NOWAK M . Strong cliques in claw-free graphs[J]. Graphs and Combinatorics, 2021, 37 (6): 2581- 2593.
[1] 孟献青. 一类平面图的强边染色[J]. 山东大学学报（理学版）, 2015, 50(08): 10-13.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] 丁超1,2, 元昌安1,3*, 覃晓1,3. 基于GEP的多数据流预测算法[J]. J4, 2010, 45(7): 50 -54 .
[2] 张德瑜,翟文广 . 关于整数n的k次补数[J]. J4, 2006, 41(5): 4 -07 .
[3] 王廷明,黎伯堂 . 一类矩阵秩恒等式的证明[J]. J4, 2007, 42(2): 43 -45 .
[4] 付永红1 ,余眝妙2 ,唐应辉3 ,李才良4 . 两水平修理策略下的M／(Mr,Gs)／1／N／N机器维修模型稳态概率算法与性能分析[J]. J4, 2009, 44(4): 72 -78 .
[5] 孟祥波1,张立东1,杜子平2. 均值-方差标准下带跳的保险公司投资与再保险策略[J]. 山东大学学报（理学版）, 2014, 49(05): 36 -40 .
[6] 彭振华,徐义红*,涂相求. 近似拟不变凸集值优化问题弱有效元的最优性条件[J]. 山东大学学报（理学版）, 2014, 49(05): 41 -44 .
[7] 袁晖坪 . 行（列）对称矩阵的Schur分解和正规阵分解[J]. J4, 2007, 42(10): 123 -126 .
[8] 曾文赋1,黄添强1,2,李凯1,余养强1,郭躬德1,2. 基于调和平均测地线核的局部线性嵌入算法[J]. J4, 2010, 45(7): 55 -59 .
[9] 易超群,李建平,朱成文. 一种基于分类精度的特征选择支持向量机[J]. J4, 2010, 45(7): 119 -121 .
[10] 孙亮吉,吉国兴 . 上三角形矩阵代数上的Jordan(α,β)-导子和广义Jordan(α,β)-导子[J]. J4, 2007, 42(10): 100 -105 .
版权所有 © 2018 《山东大学学报(理学版)》编辑部　
地址: 山东省济南市山大南路27号山东大学中心校区（250100）　电话: +86-0531-88366917　E-mail: xblxb@sdu.edu.cn
本系统由北京玛格泰克科技发展有限公司设计开发