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
|
Journal Supporters
|