Noon lecture

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

On 22.06.2006 at 12:20 in S5, there is the following noon lecture:

The Complexity of Some Restricted H-Colouring Problems

Mark Siggers

Abstract

We look first at the problem of H-Colouring for instances G of bounded degree. Let b(H) be the minimum integer for which the problem of H-Colouring is NP-complete for graphs G of maximum degree 3. We look at bounds on b(H) for various graphs H, and observe that a small alteration of Hell and Ne\v{s}et\v{r}il's proof of the H-colouring dichotomy shows that b(H) is finite for any non-bipartite graph H. This supports a more general conjecture of Feder, Hell, and Huang, about NP-complete homomorphism problems remaining NP-complete even when large enough finite degree constraints are added.

Time permitting, we will also look at some results on the H-colouring problem when restricted to planar instances G.

list of noon lectures ( 2005 | 2006 | 2007 | 2008 | 2009 | 2010 | 2011 | 2012 | 2013 | 2014 | 2015 | 2016 | 2017 | future lectures)

Webmaster: kamweb.mff.cuni.cz         Modified: 19. 10. 2010