Français Anglais
Accueil Annuaire Plan du site
Accueil > Evenements > Séminaires
Séminaire d'équipe(s)
Homomorphism and minor of signed bipartite graphs
Reza Naserasr

12 April 2013, 10h30 - 12 April 2013, 11h30
Salle/Bat : 475/PCRI-N
Contact :

Activités de recherche :

Résumé :
A signature on a graph is an assignment of signs (+ or -) to the edges. Resigning at a vertex $x$ is to change the signs of all the edges incident $x$. Let $Sigma$ be the set of negative edges. Two signatures $Sigma_1$ and $Sigma_2$ on a same graph are said to be equivalent if one can be obtained from the other by a sequence of resigning. A signed graph, denoted $(G, Sigma)$ is a graph together with a set of equivalent signatures.

A singed minor of $(G,Sigma)$ is a signed graph obtained from $(G,Sigma)$ by a sequence of (i) deleting edges or vertices, (ii) contracting positive edges and (iii) resigning. A homomorphism of $(G, Sigma)$ to $(H, Sigma_1)$ is homomorphism of $G$ to $H$ which preserves signs of edges with respect to some signatures $Sigma'$ and $Sigma_1'$ equivalent to $Sigma$ and $Sigma_1$ respectively.

In this talk we show that homomorphism of signed bipartite graphs captures the notion of graph homomorphisms. Thus many coloring theories on graphs can be extend to this set of signed graphs. In particular we consider possible extensions of Hadwiger's conjecture. We also show some results on the complexity of homomorphism problem for this set of signed graphs.

Pour en savoir plus : https://www.lri.fr/~reza/
Séminaires
A Family of Tractable Graph Distances
Gestion de données du Web
Wednesday 04 July 2018 - 10h30
Salle : 465 - PCRI-N
Stratis Ioannidis .............................................

Binary pattern of length greater than 14 are abeli
Combinatoire
Friday 29 June 2018 - 14h30
Salle : 445 - PCRI-N
Matthieu Rosenfeld .............................................

Distributionally Robust Optimization with Principa
Optimisation combinatoire et stochastique
Friday 29 June 2018 - 11h00
Salle : 455 - PCRI-N
Dr. Jianqiang Cheng .............................................

Caractérisation de réseaux égocentrés par l'énumér
Friday 15 June 2018 - 14h30
Salle : 455 - PCRI-N
Raphaël Charbey .............................................

DATA VERACITY ASSESSMENT: HOW A-PRIORI KNOWLEDGE E
Intégration de données et de connaissances
Friday 15 June 2018 - 14h00
Salle : 445 - PCRI-N
Valentina Beretta .............................................