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

DOI10.7151/DMGT.1624zbMATH Open1257.05047arXiv1005.2816OpenAlexW2012113004MaRDI QIDQ4648784FDOQ4648784

Authors: Éric Sopena 

Publication date: 16 November 2012

Published in: Discussiones Mathematicae Graph Theory (Search for Journal in Brave)

Abstract: The oriented chromatic number of an oriented graph $vecG$ is the minimum order of an oriented graph $vevH$ such that $vecG$ admits a homomorphism to $vevH$. 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 $vevU$ such that every orientation $vecG$ of $G$ admits a homomorphism to $vecU$. 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.

Full work available at URL: https://arxiv.org/abs/1005.2816

Recommendations

• Oriented chromatic number of Cartesian products \(P_m \square P_n\) and \(C_m \square P_n \)
• The chromatic number of oriented graphs
• Oriented chromatic number of Cartesian products and strong products of paths
• Oriented graph coloring
• Acyclic and oriented chromatic numbers of graphs

zbMATH Keywords

product graphoriented chromatic numberoriented coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Paths and cycles (05C38) Graph operations (line graphs, products, etc.) (05C76)

Cited In (5)

• On the oriented coloring of the disjoint union of graphs
• On the oriented coloring of the disjoint union of graphs
• Oriented chromatic number of Cartesian products and strong products of paths
• Oriented chromatic number of Cartesian products \(P_m \square P_n\) and \(C_m \square P_n \)
• On the oriented achromatic number of graphs

This page was built for publication: Upper oriented chromatic number of undirected graphs and oriented colorings of product graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4648784)