H-colouring Pt-free graphs in subexponential time

H-colouring Pt-free graphs in subexponential time

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

书目详细资料
Main Authors:	Groenland, C, Okrasa, K, Rzążewski, P, Scott, A, Seymour, P, Spirkl, S
格式:	Journal article
语言:	English
出版:	Elsevier 2019

相似书籍

Subexponential Parameterized Algorithms on Graphs of Bounded Genus and H-minor-free Graphs
由: Demaine, Erik D., et al.
出版: (2023)

Pseudodeterministic constructions in subexponential time
由: Oliveira, I, et al.
出版: (2017)

Learning Mixtures of Linear Regressions in Subexponential Time via Fourier Moments
由: Chen, Sitan, et al.
出版: (2022)

Clique covers of H-free graphs
由: Nguyen, T, et al.
出版: (2023)

Maximising H-colourings of graphs
由: Guggiari, H, et al.
出版: (2019)

Query-efficient locally decodable codes of subexponential length
由: Chee, Yeow Meng, et al.
出版: (2012)

Pure pairs. VIII. Excluding a sparse graph
由: Scott, A, et al.
出版: (2024)

Pure pairs. IV. Trees in bipartite graphs
由: Scott, AD, et al.
出版: (2023)

Bipartite graphs with no K6 minor
由: Chudnovsky, M, et al.
出版: (2023)

Erdős–Hajnal for graphs with no 5-hole
由: Chudnovsky, M, et al.
出版: (2023)

Concatenating bipartite graphs
由: Chudnovsky, M, et al.
出版: (2022)

Pure pairs. II. Excluding all subdivisions of a graph
由: Chudnovsky, M, et al.
出版: (2021)

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
由: Chudnovsky, M, et al.
出版: (2019)

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes
由: Chudnovsky, M, et al.
出版: (2019)

Towards Erdős-Hajnal for graphs with no 5-hole
由: Chudnovsky, M, et al.
出版: (2019)

Improved hardness for H-colourings of G-colourable graphs
由: Wrochna, M, et al.
出版: (2020)

Asymptotics for Finite-Time Ruin Probabilities of a Dependent Bidimensional Risk Model with Stochastic Return and Subexponential Claims
由: Xiaowen Shen, et al.
出版: (2024-09-01)

Pure pairs. III. Sparse graphs with no polynomial-sized anticomplete pairs
由: Chudnovsky, M, et al.
出版: (2020)

Randomly Stopped Minimum, Maximum, Minimum of Sums and Maximum of Sums with Generalized Subexponential Distributions
由: Jūratė Karasevičienė, et al.
出版: (2024-01-01)

Size reconstructibility of graphs
由: Groenland, C, et al.
出版: (2020)

Structure for algorithms, graph reconstruction and hypercube intersections
由: Groenland, C
出版: (2020)

Balancing connected colourings of graphs
由: Illingworth, F, et al.
出版: (2023)

For most graphs H, most H-free graphs have a linear homogeneous set
由: Mcdiarmid, C, et al.
出版: (2013)

Graphs, colourings and the four-colour theorem /
由: 374980 Wilson, Robert A.
出版: (2002)

Pure pairs VI. Excluding an ordered tree
由: Scott, A, et al.
出版: (2022)

Pure pairs. VII. Homogeneous submatrices in 0/1-matrices with a forbidden submatrix
由: Scott, A, et al.
出版: (2023)

Pure pairs. V. Excluding some long subdivision
由: Scott, A, et al.
出版: (2023)

Polynomial bounds for chromatic number. iv: a near-polynomial bound for excluding the five-vertex path
由: Scott, A, et al.
出版: (2023)

Polynomial bounds for chromatic number. I: excluding a biclique and an induced tree
由: Scott, A, et al.
出版: (2022)

Polynomial bounds for chromatic number II: excluding a star-forest
由: Scott, A, et al.
出版: (2022)

Polynomial bounds for chromatic number III: excluding a double star
由: Scott, A, et al.
出版: (2022)

Monochromatic Cycles in 2-Coloured Graphs
由: Benevides, F, et al.
出版: (2012)

Colourings of random graphs
由: Heckel, A
出版: (2016)

Clique colouring of binomial random graphs
由: McDiarmid, C, et al.
出版: (2018)

Exceptional graphs for the random walk
由: Aru, J, et al.
出版: (2020)

Clustered colouring in minor-closed classes
由: Norin, S, et al.
出版: (2019)

Graph colourings and games
由: Meeks, KFT
出版: (2012)

Edge colourings of graphs /
由: 347791 Fiorini, S., et al.
出版: (1977)

Improper colourings of graphs
由: Kang, R
出版: (2008)

Pure pairs. IX. Transversal trees
由: Scott, A, et al.
出版: (2024)