\(H\)-colouring \(P_t\)-free graphs in subexponential time

DOI10.1016/j.dam.2019.04.010zbMath1419.05074arXiv1803.05396MaRDI QIDQ2322884

Sophie Spirkl, Karolina Okrasa, Carla Groenland, P. D. Seymour, Paweł Rzążewski, Alexander D. Scott

Publication date: 5 September 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1803.05396

zbMATH Keywords

partition function; colouring; path-decomposition; subexponential-time algorithm; \(P_t\)-free graph

Mathematics Subject Classification ID

05A15: Exact enumeration problems, generating functions

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Unnamed Item, Finding Large $H$-Colorable Subgraphs in Hereditary Graph Classes, Colouring (P_r+P_s)-Free Graphs, Colouring H-free graphs of bounded diameter., Unnamed Item, Approximately coloring graphs without long induced paths, On cycle transversals and their connected variants in the absence of a small linear forest, On the Maximum Weight Independent Set Problem in Graphs without Induced Cycles of Length at Least Five, Unnamed Item, Complexity of \(C_k\)-coloring in hereditary classes of graphs, Connected greedy coloring of \(H\)-free graphs, Colouring generalized claw-free graphs and graphs of large girth: bounding the diameter, Colouring \((P_r + P_s)\)-free graphs, List 3-coloring graphs with no induced \(P_6 + rP_3\), Covering minimal separators and potential maximal cliques in \(P_t\)-free graphs, Subexponential algorithms for variants of the homomorphism problem in string graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sparsity. Graphs, structures, and algorithms
• Improved complexity results on \(k\)-coloring \(P_t\)-free graphs
• Deciding \(k\)-colorability of \(P_5\)-free graphs in polynomial time
• Tree-chromatic number
• On the complexity of H-coloring
• Subexponential-time algorithms for maximum independent set in \(P_t\)-free and broom-free graphs
• The restrictive \(H\)-coloring problem
• A subexponential-time algorithm for the maximum independent set problem in \(P_t\)-free graphs
• A dichotomy for minimum cost graph homomorphisms
• The Fine Details of Fast Dynamic Programming over Tree Decompositions
• Polynomial constraint satisfaction problems, graph bisection, and the Ising partition function
• The NP-Completeness of Edge-Coloring
• NP completeness of finding the chromatic index of regular graphs
• Computational Complexity
• On the complexity of \(k\)-SAT