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 条
[41]   Zero Forcing in Claw-Free Cubic Graphs [J].
Davila, Randy ;
Henning, Michael A. .
BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2020, 43 (01) :673-688
[42]   The asymptotic number of claw-free cubic graphs [J].
McKay, BD ;
Palmer, EM ;
Read, RC ;
Robinson, RW .
DISCRETE MATHEMATICS, 2003, 272 (01) :107-118
[43]   Zero Forcing in Claw-Free Cubic Graphs [J].
Randy Davila ;
Michael A. Henning .
Bulletin of the Malaysian Mathematical Sciences Society, 2020, 43 :673-688
[44]   Semipaired Domination in Claw-Free Cubic Graphs [J].
Henning, Michael A. ;
Kaemawichanurat, Pawaton .
GRAPHS AND COMBINATORICS, 2018, 34 (04) :819-844
[45]   ON HAMILTONIAN CYCLES IN CLAW-FREE CUBIC GRAPHS [J].
Mohr, Elena ;
Rautenbach, Dieter .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2022, 42 (01) :309-313
[46]   Semitotal Domination in Claw-Free Cubic Graphs [J].
Henning, Michael A. ;
Marcon, Alister J. .
ANNALS OF COMBINATORICS, 2016, 20 (04) :799-813
[47]   STRONG CHROMATIC INDEX OF CLAW-FREE GRAPHS WITH EDGE WEIGHT SEVEN1 [J].
Lin, Yuquan ;
Lin, Wensong .
DISCUSSIONES MATHEMATICAE GRAPH THEORY, 2024, 44 (04) :1311-1325
[48]   Strong edge-coloring of planar graphs with girth at least seven [J].
Yuan, Jiaxin ;
Huang, Mingfang .
ITALIAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2024, (51) :295-304
[49]   A note on path factors in claw-free graphs [J].
Zhang, Heping ;
Zhou, Shan .
ARS COMBINATORIA, 2010, 97 :87-95
[50]   A Note on Strong Edge Coloring of Sparse Graphs [J].
Dong, Wei ;
Li, Rui ;
Xu, Bao Gang .
ACTA MATHEMATICA SINICA-ENGLISH SERIES, 2019, 35 (04) :577-582