Doctorat
Equipe : Algorithmique et Complexité
Etude algorithmique et structuriel de graphes aretes-coloriées
Début le 01/12/2009
Direction : MANOUSSAKIS, Yannis
Ecole doctorale :
Etablissement d'inscription : Université Paris-Saclay
Lieu de déroulement : LRI
Soutenue le 13/12/2012 devant le jury composé de :
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.
Activités de recherche :
Résumé :
Dans cette thèse nous étudions différents problèmes de graphes et multigraphes arêtes-coloriés tels que la connexité propre, la coloration forte d'arêtes et les chaînes et cycles hamiltoniens propres. Enfin, nous améliorons l'algorithme connu $O(n^4)$ pour décider du comportement d'un graphe sous opérateur biclique, en étudiant les bicliques dans les graphes sans faux jumeaux. Plus précisément,
- Nous étudions d'abord le nombre $k$-connexité-propre des graphes, noté $pc_k(G)$, ç'est à dire le nombre minimum de couleurs nécessaires pour colorer les arêtes d'un graphe de façon à ce qu'entre chaque paire de sommets, ils existent $k$ chemins intérieurement sommet-disjoints. Nous prouvons plusieurs bornes supérieures pour $pc_k(G)$. Nous énonçons quelques conjectures pour les graphes généraux et bipartis et nous les prouvons dans le cas où $k = 1$.
- Nous étudions l'existence de chaînes et de cycles hamiltoniens propres dans les multigraphes arêtes-coloriés. Nous établissons des conditions suffisantes, en fonction de plusieurs paramètres tels que le nombre d'arêtes, le degré arc-en-ciel, la connexité, etc.
- Nous montrons que l'indice chromatique fort est linéaire au degré maximum pour tout graphe $k$-dégénéré où, $k$ est fixe. En corollaire, notre résultat conduit à une amélioration des constantes et donne également un algorithme plus simple et plus efficace pour cette famille de graphes. De plus, nous considérons les graphes planaires extérieurs. Nous donnons une formule pour trouver l'indice chromatique fort exact pour les graphes bipartis planaires extérieurs. Nous améliorons également la borne supérieure pour les graphes planaires extérieurs généraux.
- Enfin, nous étudions les bicliques dans les graphes sans faux jumeaux et nous présentons ensuite un algorithme $O(n+m)$ pour reconnaître les graphes convergents et divergents en améliorant l'algorithme $O(n^4)$.
