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 Demographic reconstruction from paleogenomes of th Thursday 25 February 2021 - 14h00 Salle : 435 - PCRI-N Nina Marchi ............................................. A Graph-based Similarity Approach to Classify Recu Thursday 18 February 2021 - 14h00 Salle : 435 - PCRI-N Coline Gianfrotta ............................................. "Answer Set Programming for computing constraints- Thursday 04 February 2021 - 14h00 Salle : 435 - PCRI-N Maxime Mahout ............................................. "Pandæsim: An Epidemic Spreading Stochastic Simula Thursday 14 January 2021 - 14h00 Salle : 435 - PCRI-N Patrick Amar ............................................. Disentangling the role of selection on the evoluti Friday 02 October 2020 - 17h30 Salle : 455 - PCRI-N Fanny Pouyet ............................................. > tous les séminaires