Generalized signed graphs of large girth and large chromatic number (Q2144578)

A classical result by \textit{P. Erdős} [Can. J. Math. 11, 34--38 (1959; Zbl 0084.39602)] asserts that for any positive integers \(k\) and \(g\), there exists a graph \(G\) with chromatic number at least \(k\) and girth at least \(g\). This paper presents an effort to generalize this classic result. Given a graph \(G\) and a set \(S\) of permutations of positive integers, an \(S\)-labelling of \(G\) is a pair \((D, \sigma)\), where \(D\) is an orientation of \(G\) and \(\sigma : E(D) \to S\) is a mapping which assigns to each arc \(e = (u, v)\) of \(D\) a permutation \(\sigma(e) \in S\). A proper \(k\)-colouring of \((D, \sigma)\) is a mapping \(f : V(G) \to [k] = {1, 2,\dots, k}\) such that \(\sigma(f(x)) \not= f(y)\) for each arc \(e = (x, y)\). A graph \(G\) is called \(S\)-\(k\)-colourable if \((D, \sigma)\) has a proper \(k\)-colouring, for every \(S\)-labelling \((D, \sigma)\) of \(G\). The \(S\)-chromatic number of a graph \(S\) is the minimum integer \(k\) such that \(G\) is \(S\)-\(k\)-colourable. It is indicated that the concept of \(S\)-\(k\)-colourable of graphs is a common generalization of classic colorings as well as coloring of signed graphs, among others. The above-mentioned classical result of Erdős is extended in this paper to the form of \(S\)-\(k\)-colourings. A permutation of \([k]\) is a partial permutation if it is a bijection between subsets of \([k]\). One of the main results in the paper shows that for any positive integers \(k\) and \(g\), and a non-trivial subset \(S\) of partial permutations of \([k]\), there is a graph with girth at least \(g\) that is not \(S\)-\(k\)-colourable. A set of permutations \(S\) is non-trivial if for every positive integer \(i\), there is a permutation \(\pi \in S\) such that \(\pi(i) = i\), and \(S\) is transitive if for every pair \((i, j)\) of positive integers, there is a permutation \(\pi \in S\) such that \(\pi(i) = j\) or \(\pi(j) = i\). Another main result in the paper indicates that for any integers \(2 \le k^\prime \le k\), \(3 \le g\) and subset \(S\) of partial permutations of \([k]\), there is a \(k^\prime\)-chromatic graph \(G\) with girth at least \(g\) that is not \(S\)-\(k\)-colourable if and only if for every \(k^\prime\)-subset \(I\) of \([k]\), there are distinct integers \(i, j \in I\) such that there is a permutation \(\pi \in S\) with \(\pi(i) = j\) or \(\pi(j) = i\). The paper ends with an open question given positive integers \(k^\prime\), \(k\), \(g\), how to determine a set \(S\) of permutations of positive integers, such that there is a graph of graphs \(G\) of girth at least \(g\) with signed chromatic number \(k^\prime\) and \(S\)-chromatic number greater than \(k\). This seems to be an interesting question.