





















Pushable homomorphisms and the pushable chromatic number $χ_p$ of oriented graphs were introduced by Klostermeyer and MacGillivray in 2004. They notably observed that, for any oriented graph $\overrightarrow{G}$, we have $χ_p(\overrightarrow{G}) \leq χ_o(\overrightarrow{G}) \leq 2 χ_p(\overrightarrow{G})$, where $χ_o(\overrightarrow{G})$ denotes the oriented chromatic number of $\overrightarrow{G}$. This stands as first general bounds on $χ_p$. This parameter was further studied in later works.This work is dedicated to the pushable chromatic number of oriented graphs fulfilling particular degree conditions. For all $Δ\geq 29$, we first prove that the maximum value of the pushable chromatic number of an oriented graph with maximum degree $Δ$ lies between $2^{\fracΔ{2}-1}$ and $(Δ-3) \cdot (Δ-1) \cdot 2^{Δ-1} + 2$ which implies an improved bound on the oriented chromatic number of the same family of graphs. For subcubic oriented graphs, that is, when $Δ\leq 3$, we then prove that the maximum value of the pushable chromatic number is~$6$ or~$7$. We also prove that the maximum value of the pushable chromatic number of oriented graphs with maximum average degree less than~$3$ lies between~$5$ and~$6$. The former upper bound of~$7$ also holds as an upper bound on the pushable chromatic number of planar oriented graphs with girth at least~$6$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。