List star edge-coloring of claw-free subcubic multigraphs
type: Item
instance of: scholarly article
title: List star edge-coloring of claw-free subcubic multigraphs
zbMATH Open document ID: 1481.05042
author: Qing Cui
author: Zhenmeng Han
published in: Discrete Applied Mathematics
publication date: 2022-01-13T00:00:00Z
review text: The star chromatic index \(\chi^\prime_{st}(G)\) of a graph \(G\) is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored, i.e. to get a star edge-coloring. The authors prove that the star chromatic index for claw-free subcubic multigraphs is at most 6 and show that this is tight. This gives some evidence towards a conjecture in [\textit{Z. Dvořák} et al., J. Graph Theory 72, No. 3--4, 313--326 (2013; Zbl 1262.05049)], where they conjecture that 6 is an upper bound for the star chromatic index of any subcubic multigraph. In the proof, the authors first derive certain properties (done in 6 claims) of a possible smallest counterexample. After that, they derive a contradiction by giving a star edge-coloring of \(G\) with 6 colors by extending a star-edge coloring of a subgraph of \(G\).
reviewed by: Stijn Cambie
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 7456397
zbMATH Keywords: star edge-coloring
zbMATH Keywords: star chromatic index
zbMATH Keywords: list star chromatic index
zbMATH Keywords: claw-free
zbMATH Keywords: subcubic multigraph
MaRDI profile type: Publication
full work available at URL: j.dam.2021.12.014
OpenAlex ID: W4213287048
cites work: Coloring with no 2-colored \(P_4\)'s
cites work: Star Edge Coloring of Some Classes of Graphs
cites work: An upper bound for the choice number of star edge coloring of graphs
cites work: On star edge colorings of bipartite and subcubic graphs
cites work: Star Chromatic Index
cites work: Star coloring of graphs
cites work: List star edge coloring of \(k\)-degenerate graphs
cites work: List star edge-coloring of subcubic graphs
cites work: List star edge coloring of sparse graphs
cites work: List star edge-coloring of \(k\)-degenerate graphs and \(K_4\)-minor free graphs
cites work: A survey on star edge-coloring of graphs
cites work: Star chromatic index of subcubic multigraphs
cites work: Star 5-edge-colorings of subcubic multigraphs
cites work: Upper bounds on list star chromatic index of sparse graphs
cites work: Q5322832
cites work: Note on list star edge‐coloring of subcubic graphs
cites work: A polynomial time algorithm to find the star chromatic index of trees
cites work: Edge-partition and star chromatic index
cites work: Star edge-coloring of graphs with maximum degree four
DOI: 10.1016/J.DAM.2021.12.014
description: scientific article; zbMATH DE number 7456397