On the Oriented Chromatic Number of Dense Graphs

Details On the Oriented Chromatic Number of Dense Graphs On the Oriented Chromatic Number of Dense Graphs

2006-11-28

arxiv.org/abs/math/0611865v2

Contributions to Discrete Mathematics 2(2):145-152, 2007

Mathematics

Combinatorics

Scientific paper

Let $G$ be a graph with $n$ vertices, $m$ edges, average degree $\delta$, and maximum degree $\Delta$. The "oriented chromatic number" of $G$ is the maximum, taken over all orientations of $G$, of the minimum number of colours in a proper vertex colouring such that between every pair of colour classes all edges have the same orientation. We investigate the oriented chromatic number of graphs, such as the hypercube, for which $\delta\geq\log n$. We prove that every such graph has oriented chromatic number at least $\Omega(\sqrt{n})$. In the case that $\delta\geq(2+\epsilon)\log n$, this lower bound is improved to $\Omega(\sqrt{m})$. Through a simple connection with harmonious colourings, we prove a general upper bound of $O(\Delta\sqrt{n})$ on the oriented chromatic number. Moreover this bound is best possible for certain graphs. These lower and upper bounds are particularly close when $G$ is ($c\log n$)-regular for some constant $c>2$, in which case the oriented chromatic number is between $\Omega(\sqrt{n\log n})$ and $O(\sqrt{n}\log n)$.

Affiliated with

Also associated with

No associations

Rating

On the Oriented Chromatic Number of Dense Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with On the Oriented Chromatic Number of Dense Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and On the Oriented Chromatic Number of Dense Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-350789