H-colouring Pt-free graphs in subexponential time

Carla Groenland, Karolina Okrasa, Paweł Rzążewski, Alex Scott, Paul Seymour, Sophie Spirkl

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

A graph is called Pt-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 2Otnlog(n) for n=|V(G)| in the class of Pt-free graphs G. As a corollary, we show that the number of 3-colourings of a Pt-free graph G can be found in subexponential time. On the other hand, no subexponential time algorithm exists for 4-colourability of Pt-free graphs assuming the Exponential Time Hypothesis. Along the way, we prove that Pt-free graphs have pathwidth that is linear in their maximum degree.

Original languageEnglish (US)
Pages (from-to)184-189
Number of pages6
JournalDiscrete Applied Mathematics
Volume267
DOIs
StatePublished - 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<sub>t</sub>-free graphs in subexponential time'. Together they form a unique fingerprint.

  • Cite this

    Groenland, C., Okrasa, K., Rzążewski, P., Scott, A., Seymour, P., & Spirkl, S. (2019). H-colouring Pt-free graphs in subexponential time. Discrete Applied Mathematics, 267, 184-189. https://doi.org/10.1016/j.dam.2019.04.010