On star edge colorings of bipartite and subcubic graphs

Abstract

A star edge coloring of a graph is a proper edge coloring with no $2$-colored path or cycle of length four. The star chromatic index ${\chi }_{st}^{\prime }(G)$ of $G$ is the minimum number $t$ for which $G$ has a star edge coloring with $t$ colors. We prove upper bounds for the star chromatic index of complete bipartite graphs; in particular we obtain tight upper bounds for the case when one part has size at most $3$. We also consider bipartite graphs $G$ where all vertices in one part have maximum degree $2$ and all vertices in the other part has maximum degree $b$. Let $k$ be an integer ($k\ge 1$), we prove that if $b=2k+1$ then ${\chi }_{st}^{\prime }(G)\le 3k+2$; and if $b=2k$, then ${\chi }_{st}^{\prime }(G)\le 3k$; both upper bounds are sharp. Finally, we consider the well-known conjecture that subcubic graphs have star chromatic index at most $6$; in particular we settle this conjecture for cubic Halin graphs.

18 pages

References in corpus (2)

• Star 5-edge-colorings of subcubic multigraphs
• Note on list star edge-coloring of subcubic graphs