Etude de graphes arête-coloriés.

Currently I am teaching assistent at Engineering school \"ENSIIE\" at Evry. During my PhD, I have studied the design and analysis of polynomial and approximation algorithms for problems in graph theory.

My supervisor is Yannis Manoussakis and together we worked on "edge-colored graphs" that is a powerful tool to model real live problems.

The goal is to find edge-colored subgraphs with a specific pattern. One of the most natural patterns is one of "properness". A subgraph of an edge-colored graph is said to be properly edge-colored (or just proper) if any two incident edges in this subgraph differ in color.

The problem I have focused on during my PhD is one of the most studied in graph theory - the Maximum Tree problem. This problem was studied for simple general graphs, for directed graphs, and for weighted and unweighted case namely. Several polynomial time algorithms were proposed, as well as approximation algorithms for NP-Complete versions.

A tree in an edge-colored graph is a subgraph such that its underlying non-colored graph is connected and acyclic. A spanning tree is the one covering all vertices of an edge-colored graph. A tree is proper if no two incident edges are of the same color. A tree T in an edge-colored graph with fixed root r is said to be weakly proper if every path in T, from the root r to any leaf, is a proper one. Notice that in the case of weak proper trees, incident edges may have the same color, while this may not happen for proper trees.

We consider maximum properly edge-colored trees and maximum weak proper trees in edge-colored graphs from graph theoretic as well as algorithmic viewpoints. We prove their optimization versions to be NP-hard in general and provide algorithms for graphs without properly edge-colored cycles. We also derive some non-approximability bounds. See [1].

The main interest is to find approximation algorithms for these problems.

We started by studying various families of edge-colored graphs. We expect these results to help us to find an approach to approximate our problem.

We found a polynomial time algorithm for both problems in the case of the acyclic edge-colored graphs [1]. But the problem remains NP-Complete in the case of another families, such as in the case of the complete edge-colored graphs.
Since the results that we found were not relevant for the approximation algorithm we changed our strategy. We found sufficient conditions for the existence of spanning trees of both patterns in edge-colored graphs [2].

As the connectivity plays an important role as sufficient condition for the existence of spanning (weak) proper trees, we studied the minimum number of colors needed to guarantee the color-connectivity [4].

Further, we found sufficient conditions for the Proper Hamiltonian Path problem in edge-colored graphs, since a proper Hamiltonian path is also a proper and weak tree in same time [3].
.

[ 1 ]. "Maximum colored trees in edge-colored graphs" submitted Discrete Mathematics
V. Borozan, W. Fernandez de la Vega, Y. Manoussakis, C. A. Martinhon, R. Muthu and R. Saad