Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Details Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

2010-05-17

arxiv.org/abs/1005.2816v1

Computer Science

Discrete Mathematics

14 pages

Scientific paper

The oriented chromatic number of an oriented graph $\vec G$ is the minimum order of an oriented graph $\vev H$ such that $\vec G$ admits a homomorphism to $\vev H$. The oriented chromatic number of an undirected graph $G$ is then the greatest oriented chromatic number of its orientations. In this paper, we introduce the new notion of the upper oriented chromatic number of an undirected graph $G$, defined as the minimum order of an oriented graph $\vev U$ such that every orientation $\vec G$ of $G$ admits a homomorphism to $\vec U$. We give some properties of this parameter, derive some general upper bounds on the ordinary and upper oriented chromatic numbers of Cartesian, strong, direct and lexicographic products of graphs, and consider the particular case of products of paths.

Affiliated with

Also associated with

No associations

Rating

Upper oriented chromatic number of undirected graphs and oriented colorings of product 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 Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-297753