Chargement...
 

Algorithmics-Graphs-Combinatorics

Domaine
Algorithmics-Graphs-Combinatorics
Domain - extra
Année
2014
Starting
September 2014
État
Open
Sujet
Homomorphisms and partitions of signed digraphs
Thesis advisor
MANOUSSAKIS Yannis
Co-advisors
Reza Naserasr
Laboratory
Collaborations
Abstract
Homomorphism of graphs is a way of generalizing graph coloring results of algebraic flavor. When mixed with a geometric restriction, such graphs embeddable on a surface or more generally a minor closed family, we have some of most challenging problems in graph theory, such as the four color theorem and the Hadwiger's conjecture. The main difficulty here is that the relation between minor and homomorphism is non intuitive.

To address this issue, theory of signed graphs is used. Nottion of minor is extended for signed graphs and certain coloring results are obtained on classes of (signed) graphs satisfying certain minor properties. We have therefore recently started studying the theory of homomorphisms for signed graphs. Thus many of coloring and homomorphism results can be substaintially stengthened and therefore we have a rich and promising subject of study.

We would also consider the extention to signed digraphs, a notion which is not studied much yet and is promising.



Context
Objectives
Work program
We will do a mix of learning and research. We will spend some time on theaching the student the notion of homomorphism and minor for signed graphs. Then after having several research problems in mind we will read more on the problem to learn and do research at the same time.
Extra information
Prerequisite
Some graduate cours in graph and main mathematical course in particular linear algebra.
Détails
Expected funding
Institutional funding
Status of funding
Expected
Candidates
Maria Abi Aad
Utilisateur
reza.naserasr
Créé
Samedi 07 juin 2014 16:03:16 CEST
dernière modif.
Samedi 07 juin 2014 17:14:52 CEST

Fichiers joints

 filenamecrééhitsfilesize 
Aucun fichier joint à cette fiche


Ecole Doctorale Informatique Paris-Sud


Directrice
Nicole Bidoit
Assistante
Stéphanie Druetta
Conseiller aux thèses
Dominique Gouyou-Beauchamps

ED 427 - Université Paris-Sud
UFR Sciences Orsay
Bat 650 - aile nord - 417
Tel : 01 69 15 63 19
Fax : 01 69 15 63 87
courriel: ed-info à lri.fr