H-colouring Pt-free graphs in subexponential time

Author: 

Groenland, C
Okrasa, K
Rzążewski, P
Scott, A
Seymour, P
Spirkl, S

Publication Date: 

11 May 2019

Journal: 

Discrete Applied Mathematics

Last Updated: 

2020-11-17T15:08:02.117+00:00

Volume: 

267

DOI: 

10.1016/j.dam.2019.04.010

page: 

184-189

abstract: 

A graph is called P t -free if it does not contain the path on t vertices as an induced subgraph. Let H be a multigraph with the property that any two distinct vertices share at most one common neighbour. We show that the generating function for (list)graph homomorphisms from G to H can be calculated in subexponential time 2 Otnlog(n) for n=|V(G)| in the class of P t -free graphs G. As a corollary, we show that the number of 3-colourings of a P t -free graph G can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of P t -free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that P t -free graphs have pathwidth that is linear in their maximum degree.

Symplectic id: 

905471

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article