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. 193206, 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 minmax Edge qcoloring Problem, Journal of Graph Algorithms and
Applications, vol 19(1) pp. 505528 (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

Journal Supporters
