Français Anglais
Accueil Annuaire Plan du site
Home > Research results > Dissertations & habilitations
Research results
Ph.D de

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.