Oriented chromatic number of Cartesian products \(P_m \square P_n\) and \(C_m \square P_n \) (Q2151213): Difference between revisions

An oriented graph \(\vec{G}\) is a digraph obtained from a graph \(G\) by assigning to every edge from \(G\) one of two possible directions. In this sense, \(\vec{G}\) is called an orientation of \(G\). An orientation of a complete graph is called a tournament. The oriented chromatic number \(\vec{\chi}(\vec{G})\) of an oriented graph \(\vec{G}\) is the smallest order of a tournament \(\vec{T}\) such that there is a homomorphism from \(V(\vec{G})\) to \(V(\vec{T})\). And finally, the oriented chromatic number \(\vec{\chi}(G)\) of \(G\) is the maximum oriented chromatic number taken over all orientations of \(G\). The paper in review considers oriented colorings of Cartesian products of paths with paths (called \(2\)-dimensional grids) and Cartesian products of paths with cycles (called stacked prisms). The author presents the graph \(\vec{H}_{10}\), to which there exists a homomorphism from any orientation of \(P_8 \Box P_n\) and from any orientation of \(C_m \Box P_n\), for \(m \in \{3,4,5,6,7\}\) and \(n \ge 1\). Additionally, the author also provides the graph \(\vec{T}_{16}\), to which there exists a homomorphism from any orientation of \(C_m \Box P_n\), for \(m,n \ge 1\), implying that the oriented chromatic number of stacked prisms is at most \(16\).