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

DOI10.1137/0404035MaRDI QIDQ3977296zbMATH OpenOpenAlexFDO

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

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)

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

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
• scientific article; zbMATH DE number 434895 (Why is no real title available?)
• 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)