On the chromatic number of an oriented matroid
Recently, two distinct generalizations of a chromatic number have been proposed for oriented matroids. The oriented chromatic number \(\chi_o\) of \textit{L. A. Goddyn, M. Tarsi} and \textit{C.-Q. Zhang} [J. Graph Theory 28, No.\,3, 155--161 (1998; Zbl 0922.05027)] and \textit{L. Goddyn, P. Hliněný} and \textit{W. Hochstättler} [Comb. Probab. Comput. 15, No.\,4, 523--539 (2006; Zbl 1119.52016)] is a generalization of the circular chromatic number; it is not an integer in general and it is not a matroid invariant. The latter question is open for the chromatic number \(\chi\) of Hochstättler and Nešetřil which is always an integer. Let \(O\) be a loopless oriented matroid of rank \(r\). Then \(\chi_o (O)\leq r+1\) by definition. The authors give a topological argument to show \(\chi(O)\leq r+1\). Moreover, for \(r\geq3\) equality holds if and only if \(O\) is the orientation of the cycle matroid of the complete graph \(K_{r+1}\).
scientific article; zbMATH DE number 5303722