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

DOI10.1137/0404035zbMATH Open0735.68042OpenAlexW2007582202MaRDI QIDQ3977296FDOQ3977296

Authors: 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

Recommendations

• Colourings, homomorphisms, and partitions of transitive digraphs
• The Complexity of Colouring by Semicomplete Digraphs
• scientific article; zbMATH DE number 30749
• scientific article; zbMATH DE number 434895
• The effect of two cycles on the complexity of colourings by directed graphs

zbMATH Keywords

graph homomorphismNP-completenesspolynomial algorithmgraph colouringvertex-transitive graphs

Mathematics Subject Classification ID

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

Cited In (13)

• The complexity of restricted graph homomorphisms
• \(\gamma \)-cycles and transitivity by monochromatic paths in arc-coloured digraphs
• The Complexity of Colouring by Semicomplete Digraphs
• Graph homomorphisms with infinite targets
• Recolouring reflexive digraphs
• Homomorphisms to oriented cycles
• Title not available (Why is that?)
• Complexity of Paths, Trails and Circuits in Arc-Colored Digraphs
• On the complexity of colouring by superdigraphs of bipartite graphs
• On the complexity of digraph colourings and vertex arboricity
• The recognition of bound quivers using edge-coloured homomorphisms
• Hereditarily hard \(H\)-colouring problems
• Homomorphisms to oriented paths

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

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