Evènement pour le groupe GT Graphes et Applications

Date 2013-03-29  15:15-16:15
TitreThe complexity of signed graph homomorphisms. 
Résumé Signed graphs are graphs with signed edges (i.e. positive and negative) with an equivalence relation based on a re-signing operation. They have been used, for example, as a way of extending classical results in graph colouring (in relation with graph minors) or in the theory of flows. Recently, the notion of homomorphisms of signed graphs has been introduced by Bertrand Guenin and further developed by Reza Naserasr, Edita Rollova and Eric Sopena. It naturally extends the notion of homomorphisms for classical graphs to the case of signed graphs. We study the computational complexity of the $H$-signed colouring problem, i.e. the question of deciding whether a given signed graph admits a homomorphism to a fixed signed graph $H$. We settle all cases where $H$ is a cycle, and discuss the restriction where the input graph is planar. We relate these questions to the state of the art for classical graph homomorphisms. This is joint work with Reza Naserasr.  
LieuSalle 178 
OrateurFlorent Foucaud 

Aucun document lié à cet événement.

Retour à l'index