List star edge-coloring of claw-free subcubic multigraphs (Q2065794): Difference between revisions

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\).