On star edge colorings of bipartite and subcubic graphs
Carl Johan Casselgren, Jonas B. Granholm, André Raspaud · Discrete Applied Mathematics · 2021
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 χst′(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 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≥1); we prove that if b=2k+1, then χst′(G)≤3k+2; and if b=2k, then χst′(G)≤3k; both upper bounds are sharp. We also consider complete bipartite graphs; in particular we determine the star chromatic index of such graphs when one part has size at most 3, and prove upper bounds for the general case. 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.