On the oriented chromatic number of graphs with given excess (Q2497471): Difference between revisions

Given an oriented graph \(\vec{G}\) (that is, a directed graph without opposite arcs), the oriented chromatic number \(\chi(\vec{G})\) of \(\vec{G}\) is the smallest integer \(k\) for which there exists a mapping \(c:\;V(\vec{G}) \to \{1,2,\dots, k\}\) such that, for each \(uv \in E(\vec{G})\), \(c(u) \neq c(v)\) and, for each \(uv, wt \in E(\vec{G})\), \(c(u) = c(t) \Rightarrow c(v) \neq c(w)\). In the paper under review, the authors study the ordinary and the oriented chromatic number of undirected/oriented graphs with given excess (that is, the minimum number of edges whose deletion results in a forest; this invariant is called also the cyclomatic or Betti number, or the dimension of the cycle space of a graph). They prove that each unoriented graph \(G\) with excess \(k\) satisfies \(\chi(G) \leq \frac{1}{2}(3 + \sqrt{1 + 8k})\) and the bound is tight. Further, they prove that the oriented chromatic number of oriented graphs with excess \(k\) is at most \(k+3\) except for graphs having excess 1 and containing a directed cycle on 5 vertices (which have oriented chromatic number 5); the bound is tight for \(k \leq 4\). Finally, it is proved that, for oriented graphs with excess \(k \geq 3\cdot 2^{n-1}(2n-3)+4\), the oriented chromatic number is at least \(3\cdot 2^n - 1\).