Edge k-q-colorability of graphs
Time: 14:00 -- Location: LRI, 445
summary: 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. We first fix k = 2 and give an O(min {m²(n/log m)^(1/2), nm^(3/2)})-
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 n)²)-time algorithm constructing such a decomposition.
This is joint work with Odile Favaron and Mekkia Kouider.