The complexity of colouring symmetric relational systems
type: Item
instance of: scholarly article
title: The complexity of colouring symmetric relational systems
zbMATH Open document ID: 0810.05025
DOI: 10.1016/0166-218X(94)90203-8
published in: Discrete Applied Mathematics
publication date: 1995-04-09T00:00:00Z
review text: A relational system, \(S\), is a set \(T\) together with relations \(R_ 1,R_ 2,\dots, R_ k\) on \(T\), denoted \(S= (T,R_ 1,R_ 2,\dots, R_ k)\). In this paper the author considers the case where all the relations are binary, symmetric and antireflexive. For each of the relations \(R_ i\), the tuple \((T,R_ i)\) corresponds to an undirected graph without loops. This motivates the definition of the underlying graph \(G\) of a relational system \(S= (T,R_ 1,R_ 2,\dots, R_ k)\). Namely, this is the graph with vertex set \(V(G)= T\) and \(uv\in E(G)\) if \((u,v)\in R_ i\) for some \(i\). In this way one can talk about relational systems that are connected, bipartite, etc. by considering the underlying graph. In particular, the terms path (tree) will be used to mean a relational system whose underlying graph is a path (tree). There is also a need to distinguish between edges coming from different relations. To this end, let \(E_ i(G)= \{uv: (u,v)\in R_ i\}\) be the set of edges coloured \(i\). Then \(E(G)= E_ 1(G)\cup\cdots\cup E_ k(G)\). Thus we can present the relational system defined by \((T,R_ 1,R_ 2,\dots, R_ k)\) in the form of a coloured graph consisting of \(V(G)\) together with \(E_ 1(G),E_ 2(G),\dots, E_ k(G)\). Let \(G\) and \(H\) be two relational systems. A homomorphism from \(G\) to \(H\), denoted \(G\to H\), is a mapping \(f: V(G)\to V(H)\) such that if \(g_ 1 g_ 2\in E_ i(G)\), then \(f(g_ 1)f(g_ 2)\in E_ i(H)\) for \(i= 1,2,\dots, k\). The relational system \(f(G)\) has vertex set \[ V(f(G))= \{h\in V(H):\text{ there exists }g\in V(G)\text{ such that } f(g)= h\} \] and edge sets \[ E_ i(f(G))= \{h_ 1 h_ 2\in E_ i(H):\text{ there exists }g_ 1 g_ 2\in E_ i(G)\text{ such that }f(g_ 1) f(g_ 2)= h_ 1 h_ 2\}. \] A homomorphism \(G\to H\) is called an \(H\)-colouring of \(G\). The motivation for this name is the fact that an \(n\)-colouring of a graph \(G\) is just a homomorphism \(G\to K_ n\). The author considers the complexity of the following problem. Here …
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 08A02
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 590197
zbMATH Keywords: relational system
zbMATH Keywords: underlying graph
zbMATH Keywords: coloured graph
zbMATH Keywords: \(H\)-colouring
zbMATH Keywords: NP- complete
author: Richard C. Brewster
reviewed by: Jørgen Bang-Jensen
MaRDI profile type: Publication
cites work: The effect of two cycles on the complexity of colourings by directed graphs
cites work: The Complexity of Colouring by Semicomplete Digraphs
cites work: Q4198056
cites work: On the complexity of H-coloring
cites work: The Categorical Product of Graphs
full work available at URL: 0166-218x(94)90203-8
OpenAlex ID: W2014922252
description: scientific article; zbMATH DE number 590197