On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs

DOI10.1137/0404035zbMath0735.68042OpenAlexW2007582202MaRDI QIDQ3977296

Gary McGillivray

Publication date: 25 June 1992

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

Full work available at URL: https://doi.org/10.1137/0404035

zbMATH Keywords

NP-completenessgraph colouringgraph homomorphismpolynomial algorithmvertex-transitive graphs

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graphs and abstract algebra (groups, rings, fields, etc.) (05C25) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Related Items (6)

Graph homomorphisms with infinite targets ⋮ Homomorphisms to oriented paths ⋮ The complexity of restricted graph homomorphisms ⋮ On the complexity of colouring by superdigraphs of bipartite graphs ⋮ Hereditarily hard \(H\)-colouring problems ⋮ Homomorphisms to oriented cycles

This page was built for publication: On the Complexity of Colouring by Vertex-Transitive and Arc-Transitive Digraphs