Home Issues About JGAA Instructions for Authors
 
DOI: 10.7155/jgaa.00464
Edge $k$-$q$-Colorability of Graphs
Selma Djelloul, Odile Favaron, and Mekkia Kouider
Vol. 22, no. 2, pp. 193-206, 2018. Regular paper.
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.
Submitted: July 2017.
Reviewed: March 2018.
Revised: March 2018.
Accepted: March 2018.
Final: March 2018.
Published: March 2018.
Communicated by Xin He
article (PDF)
BibTeX