Journal article
H-colouring Pt-free graphs in subexponential time
- 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.
- Publication status:
- Published
- Peer review status:
- Peer reviewed
Actions
Access Document
- Files:
-
-
(Preview, Accepted manuscript, pdf, 217.6KB, Terms of use)
-
- Publisher copy:
- 10.1016/j.dam.2019.04.010
Authors
- Publisher:
- Elsevier
- Journal:
- Discrete Applied Mathematics More from this journal
- Volume:
- 267
- Pages:
- 184-189
- Publication date:
- 2019-05-11
- Acceptance date:
- 2019-04-17
- DOI:
- ISSN:
-
0166-218X
- Language:
-
English
- Keywords:
- Pubs id:
-
pubs:905471
- UUID:
-
uuid:b6a20530-f5c1-4329-8af7-ba47d298e70d
- Local pid:
-
pubs:905471
- Source identifiers:
-
905471
- Deposit date:
-
2019-05-28
Terms of use
- Copyright holder:
- Elsevier B.V.
- Copyright date:
- 2019
- Rights statement:
- © 2019 Elsevier B.V.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Elsevier at https://doi.org/10.1016/j.dam.2019.04.010
If you are the owner of this record, you can report an update to it here: Report update to this record