On the chromatic number of an oriented matroid
type: Item
instance of: scholarly article
title: On the chromatic number of an oriented matroid
zbMATH Open document ID: 1154.05016
author: Winfried. Hochstättler
author: Robert M. Nickel
published in: Journal of Combinatorial Theory. Series B
publication date: 2008-07-24T00:00:00Z
review text: 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}\).
Mathematics Subject Classification ID: 05B35
zbMATH DE Number: 5303722
zbMATH Keywords: oriented matroids
zbMATH Keywords: flow lattice
zbMATH Keywords: oriented chromatic number
zbMATH Keywords: circular chromatic number
zbMATH Keywords: nowhere zero flows
reviewed by: Kelly J. Pearson
MaRDI profile type: Publication
full work available at URL: j.jctb.2007.10.004
OpenAlex ID: W2039301971
cites work: Oriented Matroids
cites work: Q4871765
cites work: Oriented matroids
cites work: On (k,d)-colorings and fractional nowhere-zero flows
cites work: Balanced Signings and the Chromatic Number of Oriented Matroids
cites work: Q5663020
cites work: Antisymmetric flows in matroids
cites work: Q3135082
DOI: 10.1016/J.JCTB.2007.10.004
description: scientific article; zbMATH DE number 5303722