A note on strong edge-coloring of claw-free cubic graphs

被引:0
作者
Zhenmeng Han
Qing Cui
机构
[1] Nanjing University of Aeronautics and Astronautics,School of Mathematics
来源
Journal of Applied Mathematics and Computing | 2023年 / 69卷
关键词
Strong edge-coloring; Strong chromatic index; Claw-free; Cubic graph; 05C15;
D O I
暂无
中图分类号
学科分类号
摘要
A strong edge-coloring of a graph G is an edge-coloring of G such that any two edges that are either adjacent to each other or adjacent to a common edge receive distinct colors. The strong chromatic index of G, denoted by χs′(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi '_s(G)$$\end{document}, is the minimum number of colors needed to guarantee that G admits a strong edge-coloring. For any integer n≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 3$$\end{document}, let Hn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_n$$\end{document} denote the n-prism (i.e., the Cartesian product Cn□K2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C_n\square K_2$$\end{document}) and HnΔ\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_n^{\Delta }$$\end{document} the graph obtained from Hn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$H_n$$\end{document} by replacing each vertex with a triangle. Recently, Lin and Lin (2022) asked whether χs′(HnΔ)=6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\chi '_s(H_n^{\Delta })=6$$\end{document} for any n≥3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n\ge 3$$\end{document}. In this short note, we answer this question in the affirmative.
引用
收藏
页码:2503 / 2508
页数:5
相关论文
共 50 条
[21]   Recent progress on strong edge-coloring of graphs [J].
Deng, Kecai ;
Yu, Gexin ;
Zhou, Xiangqian .
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2019, 11 (05)
[22]   A note on 2-bisections of claw-free cubic graphs [J].
Abreu, Marien ;
Goedgebeur, Jan ;
Labbate, Domenico ;
Mazzuoccolo, Giuseppe .
DISCRETE APPLIED MATHEMATICS, 2018, 244 :214-217
[23]   Semitotal Domination in Claw-Free Cubic Graphs [J].
Zhu, Enqiang ;
Shao, Zehui ;
Xu, Jin .
GRAPHS AND COMBINATORICS, 2017, 33 (05) :1119-1130
[24]   Semitotal Domination in Claw-Free Cubic Graphs [J].
Enqiang Zhu ;
Zehui Shao ;
Jin Xu .
Graphs and Combinatorics, 2017, 33 :1119-1130
[25]   Note on injective edge-coloring of graphs [J].
Miao, Zhengke ;
Song, Yimin ;
Yu, Gexin .
DISCRETE APPLIED MATHEMATICS, 2022, 310 :65-74
[26]   Counting claw-free cubic graphs [J].
Palmer, Edgar M. ;
Read, Ronald C. ;
Robinson, Robert W. .
2003, Society for Industrial and Applied Mathematics Publications (16) :65-73
[27]   Counting claw-free cubic graphs [J].
Palmer, EM ;
Read, RC ;
Robinson, RW .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2003, 16 (01) :65-73
[28]   COLORING CLAW-FREE GRAPHS WITH Δ-1 COLORS [J].
Cranston, Daniel W. ;
Rabern, Landon .
SIAM JOURNAL ON DISCRETE MATHEMATICS, 2013, 27 (01) :534-549
[29]   On (s, t)-relaxed strong edge-coloring of graphs [J].
Dan He ;
Wensong Lin .
Journal of Combinatorial Optimization, 2017, 33 :609-625
[30]   Strong Edge-Coloring of Pseudo-Halin Graphs [J].
Li, Xiangwen ;
Lv, Jian-Bo .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2020, 43 (01) :893-910