Graph homomorphism, monotone classes and bounded pathwidth

DOI10.1007/978-3-031-64309-5_19MaRDI QIDQ7030902zbMATH OpenFDO

Authors Tala Eagling-Vose, Barnaby Martin, Daniël Paulusma, Siani Smith

Publication date 7 February 2025

Full work available at URL https://doi.org/10.1007/978-3-031-64309-5_19

zbMATH Keywords

monotone classespathwidthquantified constraint satisfaction problemsequential colouring construction gametreedepthvertex separation number

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10)

Cites work

• \textsc{max-cut} and containment relations in graphs
• An algorithmic framework for locally constrained homomorphisms
• Bounded-width QBF is PSPACE-complete
• Coloring graphs characterized by a forbidden subgraph
• Feedback vertex set and even cycle transversal for H-free graphs: finding large block graphs
• Graph minors. III. Planar tree-width
• scientific article; zbMATH DE number 4204394 (Why is no real title available?)
• scientific article; zbMATH DE number 1979486 (Why is no real title available?)
• scientific article; zbMATH DE number 2044943 (Why is no real title available?)
• List coloring in the absence of two subgraphs
• Locally constrained graph homomorphisms -- structure, complexity, and applications
• Locally constrained homomorphisms on graphs of bounded treewidth and bounded degree
• NP-hard graph problems and boundary classes of graphs
• ON THE COMPLEXITY OF SOME COLORING GAMES
• Polynomial-time Algorithm for Maximum Weight Independent Set on P ₆ -free Graphs
• Sparsity. Graphs, structures, and algorithms
• Structure-aware lower bounds and broadening the horizon of tractability for QBF
• The complexity of \(H\)-colouring of bounded degree graphs
• The complexity of constraint satisfaction games and QCSP
• The complexity of homomorphism and constraint satisfaction problems seen from the other side
• The vertex separation number of a graph equals its path-width
• Tree clustering for constraint networks

Cited in

(1)

• Complexity framework for forbidden subgraphs. II: Edge subdivision and the ``H-graphs

This page was built for publication: Graph homomorphism, monotone classes and bounded pathwidth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7030902)