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 条
  • [1] A note on strong edge-coloring of claw-free cubic graphs
    Han, Zhenmeng
    Cui, Qing
    JOURNAL OF APPLIED MATHEMATICS AND COMPUTING, 2023, 69 (03) : 2503 - 2508
  • [2] On Strong Edge-Coloring of Claw-Free Subcubic Graphs
    Jian-Bo Lv
    Jianxi Li
    Xiaoxia Zhang
    Graphs and Combinatorics, 2022, 38
  • [3] On Strong Edge-Coloring of Claw-Free Subcubic Graphs
    Lv, Jian-Bo
    Li, Jianxi
    Zhang, Xiaoxia
    GRAPHS AND COMBINATORICS, 2022, 38 (03)
  • [4] Injective edge-coloring of claw-free subcubic graphs
    Cui, Qing
    Han, Zhenmeng
    JOURNAL OF COMBINATORIAL OPTIMIZATION, 2024, 47 (05)
  • [5] Strong edge-coloring for cubic Hahn graphs
    Chang, Gerard Jennhwa
    Liu, Daphne Der-Fen
    DISCRETE MATHEMATICS, 2012, 312 (08) : 1468 - 1475
  • [6] List star edge-coloring of claw-free subcubic multigraphs
    Cui, Qing
    Han, Zhenmeng
    DISCRETE APPLIED MATHEMATICS, 2022, 309 : 258 - 264
  • [7] Strong edge-coloring of cubic bipartite graphs: A counterexample
    Cranston, Daniel W.
    DISCRETE APPLIED MATHEMATICS, 2022, 321 : 258 - 260
  • [8] Factors with Red–Blue Coloring of Claw-Free Graphs and Cubic Graphs
    Michitaka Furuya
    Mikio Kano
    Graphs and Combinatorics, 2023, 39
  • [9] Edge decomposition of connected claw-free cubic graphs
    Hong, Yanmei
    Liu, Qinghai
    Yu, Nannan
    DISCRETE APPLIED MATHEMATICS, 2020, 284 : 246 - 250
  • [10] Factors with Red-Blue Coloring of Claw-Free Graphs and Cubic Graphs
    Furuya, Michitaka
    Kano, Mikio
    GRAPHS AND COMBINATORICS, 2023, 39 (04)