TU Berlin

Algorithmics and Computational Complexity Research GroupTalk 07.11.2013


Page Content

to Navigation

The Complexity of Signed Graph Homomorphisms

Florent Foucaud (UPC Barcelona)

Signed graphs are graphs with signed edges (i.e. positive and negative) with an equivalence relation based on a local re-signing operation. They have been used, for example, as a way of extending classical results in graph colouring such as Hadwiger's conjecture. 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 (i.e. vertex-mappings that preserve adjacency) 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 input signed graph admits a homomorphism to a fixed target signed graph H. We settle all cases where H is non-bipartite and has no loop, and discuss some further cases. We relate these questions to the state of the art for classical graph homomorphisms.

This is joint work with Richard Brewster, Pavol Hell, Reza Naserasr.

07.11.2013 16:15
Florent Foucaud
TEL 512

Back to the research colloquium site.


Quick Access

Schnellnavigation zur Seite über Nummerneingabe