Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
Towards a trichotomy for quantified H-coloring.

Speaker: Barnaby Martin
Author(s): Barnaby Martin and Florent Madelaine
Slot: Array, 11:10-11:30, col. 5


Hell and Nesetril proved that the H-colouring problem is NP-complete
if, and only if, H is bipartite. In this paper, we investigate the
complexity of the quantified H-colouring problem (a restriction of the
quantified constraint satisfaction problem to undirected graphs). We
introduce this problem using a new two player colouring game. We prove
that the quantified H-colouring problem is: tractable, if H is
bipartite; NP-complete, if H is not bipartite and not connected; and
Pspace-complete, if H is connected and has a unique cycle, which is of
odd length. We conjecture that the last case extends to all
non-bipartite connected graphs. 

websites: Arnold Beckmann 2006-04-23