Edge k-q-colorability of graphs

-- Selma Djelloul (LISN, Galac)

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.

Category: seminars
Tags: Team seminar graphs