The complexity of colouring symmetric relational systems (Q1327221)

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 \(H\) is a given fixed relational system. \(H\)-colouring problem Instance: A relational system \(G\). Question: Does there exist an \(H\)-colouring of \(G\)? For graphs, the complexity of this problem was completely determined by \textit{P. Hell} and \textit{J. Nešetřil} [J. Comb. Theory, Ser. B 48, No. 1, 92-110 (1990; Zbl 0639.05023)]. The problem is NP-complete precisely when \(H\) is non-bipartite. For directed graphs such a nice characterization does not seem to exist. However for digraphs that are cores, i.e., have no homomorphisms to a proper induced subgraph, there is a conjecture about which problems should be NP-complete [\textit{J. Bang- Jensen} and \textit{P. Hell}, The effect of two cycles on the complexity of colourings by directed graphs, Discrete Appl. Math. 26, No. 1, 1-23 (1990; Zbl 0697.05029)]. The main result of this paper is the fact that if \(H\) is a path, then an \(H\)-colouring is polynomial and that there exist trees for which the problem is already NP-complete. In \textit{W. Gutjahr}, \textit{E. Welzl} and \textit{G. Woeginger} [Polynomial graph-colourings, Discrete Appl. Math. 35, No. 1, 29-45 (1992; Zbl 0761.05040)] examples of oriented trees for which the \(H\)-colouring problem is NP-complete are given. The NP-complete trees in the paper by Brewster are significantly smaller than those found by Gutjahr et al. in the case of oriented graphs.