On the complexity of \(H\)-colouring planar graphs

DOI10.1016/j.disc.2008.05.016zbMath1213.05094OpenAlexW2024156610MaRDI QIDQ1045065

Mark H. Siggers, Gary MacGillivray

Publication date: 15 December 2009

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

Full work available at URL: https://doi.org/10.1016/j.disc.2008.05.016

zbMATH Keywords

NP-completenessgraph homomorphismplanar graph\(H\)-colouring

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (8)

The complexity of signed graph and edge-coloured graph homomorphisms ⋮ Modulo orientations and matchings in graphs ⋮ Locally injective \(k\)-colourings of planar graphs ⋮ Unnamed Item ⋮ (Circular) backbone colouring: forest backbones in planar graphs ⋮ A Complexity Dichotomy for the Coloring of Sparse Graphs ⋮ On the Complexity of Digraph Colourings and Vertex Arboricity ⋮ Complexity of planar signed graph homomorphisms to cycles

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• On the complexity of H-coloring
• Algorithmic complexity of list colorings
• Tree-depth, subgraph coloring and homomorphism bounds
• Acyclic Homomorphisms and Circular Colorings of Digraphs

This page was built for publication: On the complexity of \(H\)-colouring planar graphs