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 条
[31]   On strong edge-coloring of graphs with maximum degree 5 [J].
Lu, Jian ;
Liu, Huiqing ;
Hu, Xiaolan .
DISCRETE APPLIED MATHEMATICS, 2024, 344 :120-128
[32]   On strong edge-coloring of graphs with maximum degree 4 [J].
Lv, Jian-Bo ;
Li, Xiangwen ;
Yu, Gexin .
DISCRETE APPLIED MATHEMATICS, 2018, 235 :142-153
[33]   Strong edge-coloring for planar graphs with large girth [J].
Chen, Lily ;
Deng, Kecai ;
Yu, Gexin ;
Zhou, Xiangqian .
DISCRETE MATHEMATICS, 2019, 342 (02) :339-343
[34]   Strong edge-coloring of 2-degenerate graphs [J].
Yu, Gexin ;
Yu, Rachel .
DISCRETE APPLIED MATHEMATICS, 2023, 336 :11-14
[35]   On (s, t)-relaxed strong edge-coloring of graphs [J].
He, Dan ;
Lin, Wensong .
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2017, 33 (02) :609-625
[36]   Strong Edge-Coloring of Pseudo-Halin Graphs [J].
Xiangwen Li ;
Jian-Bo Lv .
Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43 :893-910
[37]   From edge-coloring to strong edge-coloring [J].
Borozan, Valentin ;
Chang, Gerard Jennhwa ;
Cohen, Nathann ;
Fujita, Shinya ;
Narayanan, Narayanan ;
Naserasr, Reza ;
Valicov, Petru .
ELECTRONIC JOURNAL OF COMBINATORICS, 2015, 22 (02)
[38]   SEMITOTAL FORCING IN CLAW-FREE CUBIC GRAPHS [J].
Liang, Yi-ping ;
Chen, Jie ;
Xu, Shou-jun .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (04) :1373-1393
[39]   Semipaired Domination in Claw-Free Cubic Graphs [J].
Michael A. Henning ;
Pawaton Kaemawichanurat .
Graphs and Combinatorics, 2018, 34 :819-844
[40]   Semitotal Domination in Claw-Free Cubic Graphs [J].
Michael A. Henning ;
Alister J. Marcon .
Annals of Combinatorics, 2016, 20 :799-813