Star chromatic index of subcubic multigraphs

Abstract

The star chromatic index of a multigraph $G$, denoted ${\chi }_s^{\prime }(G)$, is the minimum number of colors needed to properly color the edges of $G$ such that no path or cycle of length four is bi-colored. A multigraph $G$ is star $k$-edge-colorable if ${\chi }_s^{\prime }(G)\le k$. Dvořák, Mohar and Šámal [Star chromatic index, J. Graph Theory 72 (2013), 313--326] proved that every subcubic multigraph is star $7$-edge-colorable. They conjectured in the same paper that every subcubic multigraph should be star $6$-edge-colorable. In this paper, we first prove that it is NP-complete to determine whether ${\chi }_s^{\prime }(G)\le 3$ for an arbitrary graph $G$. This answers a question of Mohar. We then establish some structure results on subcubic multigraphs $G$ with $\delta (G)\le 2$ such that ${\chi }_s^{\prime }(G)>k$ but ${\chi }_s^{\prime }(G-v)\le k$ for any $v\in V(G)$, where $k\in \{5,6\}$. We finally apply the structure results, along with a simple discharging method, to prove that every subcubic multigraph $G$ is star $6$-edge-colorable if $mad(G)<5/2$, and star $5$-edge-colorable if $mad(G)<24/11$, respectively, where $mad(G)$ is the maximum average degree of a multigraph $G$. This partially confirms the conjecture of Dvořák, Mohar and Šámal.

to appear in J. Graph Theory

References in corpus (1)

• Star edge coloring of some classes of graphs