## 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.

Original language | English (US) |
---|---|

Pages (from-to) | 184-189 |

Number of pages | 6 |

Journal | Discrete Applied Mathematics |

Volume | 267 |

DOIs | |

State | Published - Aug 31 2019 |

## All Science Journal Classification (ASJC) codes

- Discrete Mathematics and Combinatorics
- Applied Mathematics

## Keywords

- Colouring
- P-free
- Partition function
- Path-decomposition
- Subexponential-time algorithm

## Fingerprint

Dive into the research topics of 'H-colouring P_{t}-free graphs in subexponential time'. Together they form a unique fingerprint.