DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2018-2019): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

A. Nenca

Title:

Oriented chromatic number of Cartesian products $P_m\Box P_n$ and $C_m\Box P_n$

Source:

Discussiones Mathematicae Graph Theory

Received: 2019-06-05, Revised: 2020-01-31, Accepted: 2020-02-03, https://doi.org/10.7151/dmgt.2307

Abstract:

We consider oriented chromatic number of Cartesian products of two paths $P_m\Box P_n$ and of Cartesian products of paths and cycles, $C_m\Box P_n$. We say that the oriented graph $\overrightarrow G$ is colored by an oriented graph $\overrightarrow H$ if there is a homomorphism from $\overrightarrow G$ to $\overrightarrow H$. In this paper we show that there exists an oriented tournament $\overrightarrow H_{10}$ with ten vertices which colors every orientation of $P_8 \Box P_n$ and every orientation of $C_m \Box P_n$, for $m=3,4,5,6,7$ and $n\geq 1$. We also show that there exists an oriented graph $\overrightarrow T_{16}$ with sixteen vertices which colors every orientation of $C_m \Box P_n$.

Keywords:

graphs, oriented coloring, oriented chromatic number

PDF
Close