Edge $k$-$q$-Colorability of Graphs

Abstract

Given positive integers $k$, $q$, we say that a graph is edge $k$-$q$-colorable if its edges can be colored in such a way that the number of colors incident to each vertex is at most $q$ and that the size of a largest color class is at most $k$. The problem of minimizing $k$ for a given $q$ was considered in [T. Larjomaa and A. Popa, The min-max Edge q-coloring Problem, Journal of Graph Algorithms and Applications, vol 19(1) pp. 505-528 (2015)]. In this paper, we first fix $k=2$ and give an $O(\min\;\{m^2\sqrt{n/\log m}\;,\;nm^{1.5}\})$-time algorithm which given an arbitrary graph $G$ with $n$ vertices and $m$ edges, and a positive integer $q$ decides whether $G$ is $2$-$q$-colorable and outputs a $2$-$q$-coloring if such a coloring exists. Then, we fix $q=2$ and we focus on cubic graphs. In particular, we prove that every cubic graph admits a $4$-$2$-coloring such that the corresponding edge decomposition uses only paths. We give an $O(n\log ^2n)$-time algorithm constructing such a decomposition.