An algorithm on strong edge coloring of $K_4$-minor free graphs

Abstract

The strong chromatic index ${\chi }_s^{\prime }(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ has a proper edge $k$-coloring with the condition that any two edges at distance at most 2 receive distinct colors. It is known that ${\chi }_s^{\prime }(G)\le 3\mathrm{\Delta }–2$ for any $K_4$-minor free graph $G$ with $\mathrm{\Delta }\ge 3$. We give a polynomial algorithm in order $O(|E(G)|(n{\mathrm{\Delta }}^2+2n+14\mathrm{\Delta }))$ to strong color the edges of a $K_4$-minor free graph with $3\mathrm{\Delta }–2$ colors where $\mathrm{\Delta }\ge 3$.