The complexity of colouring symmetric relational systems

DOI10.1016/0166-218X(94)90203-8zbMath0810.05025OpenAlexW2014922252MaRDI QIDQ1327221

Richard C. Brewster

Publication date: 9 April 1995

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

Full work available at URL: https://doi.org/10.1016/0166-218x(94)90203-8

zbMATH Keywords

underlying graph\(H\)-colouringNP- completerelational systemcoloured graph

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Graph theory (including graph drawing) in computer science (68R10) Coloring of graphs and hypergraphs (05C15) Relational systems, laws of composition (08A02)

Related Items (4)

Graph modification for edge-coloured and signed graph homomorphism problems: parameterized and classical complexity ⋮ The complexity of signed graph and edge-coloured graph homomorphisms ⋮ The complexity of tropical graph homomorphisms ⋮ Complexity of planar signed graph homomorphisms to cycles

Cites Work

• The effect of two cycles on the complexity of colourings by directed graphs
• On the complexity of H-coloring
• The Complexity of Colouring by Semicomplete Digraphs
• The Categorical Product of Graphs
• Unnamed Item

This page was built for publication: The complexity of colouring symmetric relational systems