H-colouring P_t-free graphs in subexponential time
share
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. In this note, we show that for any α>1- t/2 ^-1 the generating function for (list) graph homomorphisms from G to H can be calculated in subexponential time O(2^|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-colouribility of P_t-free graphs assuming the Exponential Time Hypothesis.
READ FULL TEXT