An Algorithm for Continuously Edge Coloring a Set of Graphs


Abstract in English

As it’s known, The Graph k-Colorability Problem (GCP) is a wellknown NP-Hard Problem. This problem consists in finding the k minimum number of colors to paint the vertices of a graph in such a way that any two adjoined vertices, which are connected by an edge, have always different colors. In another words how can we color the edges of a graph in such a way that any two edges joined by a vertex have always different colors? In this paper we introduce a new effective algorithm for coloring the edges of the graph. Our proposed algorithm enables us to achieve a Continuously Edge Coloring (CEC) for a set of known graphs.

References used

BARENBOIM, L.; ELKIN, M., 2009 - Distributed (Δ+1)-coloring in linear (in Δ) time, Proceedings of the 41st Symposium on Theory of Computing, pp. 111–120, ISBN 978-1-60558-506-2
BEIGEL, R., 2005 - 3-coloring in time O(1.3289n), Journal of Algorithms, 54 (2): 168–204
BRÉLAZ, D., 1979 - New Methods to Color the Vertices of a Graph, Communications of the ACM, 22 (4): 251–256

Download