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

DOI10.7151/DMGT.1624MaRDI QIDQ4648784zbMATHOpenAlexFDO

Authors Éric Sopena

Publication date 16 November 2012

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

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

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)

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.

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

Cited in

(5)

• On the oriented coloring of the disjoint union of graphs
• Oriented chromatic number of Cartesian products and strong products of paths
• On the oriented achromatic number of graphs
• Oriented chromatic number of Cartesian products \(P_m \square P_n\) and \(C_m \square P_n \)
• On the oriented coloring of the disjoint union 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)