Ph.D

Group : Algorithms and Complexity

*Graphs and Colors: Edge-colored graphs, edge-colorings and proper connections*
Starts on 01/12/2009

Advisor : MANOUSSAKIS, Yannis

**Funding :** A

**Affiliation :** Université Paris-Sud

**Laboratory :** LRI

**Defended** on 13/12/2012, committee :

Rapporteurs :

Professeur Michel Habib - Université Paris Diderot.

Professeur Mickael Montassier - Université Montpellier 2.

Examinateurs :

Professeur Dominique Barth - Université de Versailles.

Professeur Alain Denise - Université Paris-Sud 11.

Professeur Marina Groshaus - Universidad de Buenos Aires.

Directeur :

Professeur Yannis Manoussakis - Université Paris-Sud 11.

**Research activities :**
**Abstract :**
In this thesis, we study different problems in edge-colored graphs and edge-colored multigraphs, such as proper connection, strong edge colorings, and proper hamiltonian paths and cycles. Finally, we improve the known $O(n^4)$ algorithm to decide the behavior of a graph under the biclique operator, by studying bicliques in graphs without false-twin vertices. In particular,

- We first study the $k$-proper-connection number of graphs, this is, the minimum number of colors needed to color the edges of a graph such that between any pair of vertices there exist $k$ internally vertex-disjoint paths. We denote this number $pc_k(G)$. We prove several upper bounds for $pc_k(G)$. We state some conjectures for general and bipartite graphs, and we prove all of them for the case $k=1$.

- Then, we study the existence of proper hamiltonian paths and proper hamiltonian cycles in edge-colored multigraphs. We establish sufficient conditions, depending on several parameters such as the number of edges, the rainbow degree, the connectivity, etc.

- Later, we show that the strong chromatic index is linear in the maximum degree for any $k$-degenerate graph where $k$ is fixed. As a corollary, our result leads to considerable improvement of the constants and also gives an easier and more efficient algorithm for this familly of graphs. Next, we consider outerplanar graphs. We give a formula to find exact strong chromatic index for bipartite outerplanar graphs. We also improve the upper bound for general outerplanar graphs from the $3Delta-3$ bound.

- Finally, we study bicliques in graphs without false-twin vertices and then we present an $O(n+m)$ algorithm to recognize convergent and divergent graphs improving the $O(n^4)$ known algorithm.