H-colouring Pt-free graphs in subexponential time
| Autor: | Paweł Rzążewski, Paul Seymour, Karolina Okrasa, Carla Groenland, Alex Scott, Sophie Spirkl |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Exponential time hypothesis
Applied Mathematics Multigraph 0211 other engineering and technologies Induced subgraph 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology Free graph 01 natural sciences Graph Combinatorics Pathwidth 010201 computation theory & mathematics Discrete Mathematics and Combinatorics Homomorphism Mathematics |
| Zdroj: | Discrete Applied Mathematics. 267:184-189 |
| ISSN: | 0166-218X |
| Popis: | 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 O t n log ( 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect