JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE) ›› 2024, Vol. 59 ›› Issue (2): 53-58.doi: 10.6040/j.issn.1671-9352.0.2022.557

•   • Previous Articles     Next Articles

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)

79

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

CLC Number: 

  • O157

Fig.1

Neighbors of the vertices v1, v2 (except v1, v2) in the graph G are divided into three sets of vertices D1, D2 and D3"

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] Ruiying XUE,Zongtian WEI,Meijuan ZHAI. Restricted burning connectivity of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 91-99, 109.
[2] Li ZHU,Peng LI,Aifa WANG. Study on semi-paired k-disjoint path cover of unit interval graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 80-90.
[3] Yanan SU,Chunling TONG,Yong LI,Senyuan SU. Equitable total coloring of generalized Petersen graphs P(n, k) [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 71-79.
[4] Chaofan LIANG,Fenjin LIU,Yuchao LI,Shunyi LIU. Construction of singularly cospectral graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 65-70.
[5] Yaxin SHI,Fengxia LIU,Hua CAI. On r-hued coloring of Wn□Pm [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 59-64.
[6] Huan LIU,Huiying QIANG,Hongshen WANG,Yu BAI. 2-distance sum distinguishing coloring of trees [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 47-52, 58.
[7] Jing CAO,Xiang'en CHEN. E-total coloring of wheels and fans vertex-distinguished by multiple sets [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2024, 59(2): 38-46.
[8] Tingzeng WU,Tian ZHOU. Characterizing properties of (signless) Laplacian permanental polynomials of bicyclic graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 151-160.
[9] Ying JI,Bo DENG,Haixing ZHAO,Yanlong TANG. Domination entropy based on graph operations [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 140-150.
[10] Jin LI,Changqing XU. Adjacent vertex distinguishing edge coloring of IC-planar graphs without intersecting triangles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 134-139.
[11] Longmiao XIA,Zongtian WEI,Liping DING. Burning connectivity of oriented graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(12): 127-133.
[12] Ranran WANG,Fei WEN,Shucheng ZHANG. On the generalized characteristic polynomial of a family of graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 165-174.
[13] Shuang WANG,Fang DUAN. Complete characterization of graphs with exactly two negative eigenvalues [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 160-164.
[14] Ligong WANG,Zhiming YU,Feng ZHOU,Lijie TAO,Luqi XING. Two kinds of integral graphs based on complete graphs [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 155-159.
[15] Hongjun DU,Huijuan WANG. Linear arboricity on embedded graphs without adjacent short cycles [J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2023, 58(11): 147-154.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
[1] DING Chao1, 2, YUAN Chang-an1, 3, QIN Xiao1, 3. A prediction algorithm for multi-data streams  based on GEP[J]. J4, 2010, 45(7): 50 -54 .
[2] ZHANG De-yu,ZHAI Wen-guang . [J]. J4, 2006, 41(5): 4 -07 .
[3] WANG Ting-ming,LI Bo-tang . Proof of a class of matrix rank identities[J]. J4, 2007, 42(2): 43 -45 .
[4] FU Yonghong 1, YU Miaomiao 2*, TANG Yinghui 3, LI Cailiang 4. [J]. J4, 2009, 44(4): 72 -78 .
[5] MENG Xiang-bo1, ZHANG Li-dong1, DU Zi-ping2. Investment and reinsurance strategy for insurers under #br# mean-variance criterion with jumps#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 36 -40 .
[6] PENG Zhen-hua, XU Yi-hong*, TU Xiang-qiu. Optimality conditions for weakly efficient elements of nearly preinvex set-valued optimizaton#br#[J]. JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE), 2014, 49(05): 41 -44 .
[7] YUAN Hun-ping . Schur factorization and normal matrices factorization of row (column) symmetric matrices[J]. J4, 2007, 42(10): 123 -126 .
[8] ZENG Weng-fu1, HUANG Tian-qiang1,2, LI Kai1, YU YANG-qiang1, GUO Gong-de1,2. A local linear emedding agorithm based on harmonicmean geodesic kernel[J]. J4, 2010, 45(7): 55 -59 .
[9] YI Chao-qun, LI Jian-ping, ZHU Cheng-wen. A kind of feature selection based on classification accuracy of SVM[J]. J4, 2010, 45(7): 119 -121 .
[10] SUN Liang-ji,JI Guo-xing . Jordan(α,β)-derivations and generalized Jordan(α,β)-derivations on upper triangular matrix algebras[J]. J4, 2007, 42(10): 100 -105 .
Copyright 2018 © Editorial office of JOURNAL OF SHANDONG UNIVERSITY(NATURAL SCIENCE)
Supported by Beijing Magtech Co.Ltd