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 colouringgraph homomorphismNP-completenesspolynomial algorithmvertex-transitive graphs

Mathematics Subject Classification ID

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

Review text

Given a fixed digraph \(H\), the \(H\)-colouring problem is: For a given digraph \(D\), does there exist an \(H\)-colouring of \(D\) --- that is, a function (homomorphism) \(f: V(D)\to V(H)\) such that \(f(x)f(y)\) is an arc in \(H\) whenever \(xy\) is an arc in \(D\)? The author investigates the complexity of this problem, for \(H\) either vertex-transitive or arc-transitive, obtaining a complete classification in each case. In the vertex-transitive case, the \(H\)-colouring problem is shown to be NP-complete unless \(H\) admits a retraction to a directed cycle, in which case the problem is polynomial. A similar classification for arc-transitive digraphs is deduced as a corollary.

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

(14)

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

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)