Journal article icon

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

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.dam.2019.04.010

Authors


More by this author
Institution:
University of Oxford
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0002-9878-8750
More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0003-4489-5988
Expand authors...
Publisher:
Elsevier Publisher's website
Journal:
Discrete Applied Mathematics Journal website
Volume:
267
Pages:
184-189
Publication date:
2019-05-11
Acceptance date:
2019-04-17
DOI:
ISSN:
0166-218X
Source identifiers:
905471
Language:
English
Keywords:
Pubs id:
pubs:905471
UUID:
uuid:b6a20530-f5c1-4329-8af7-ba47d298e70d
Local pid:
pubs:905471
Deposit date:
2019-05-28

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP