

























This paper considers upper bounds on the oriented chromatic number $χ_o(G)$, of an oriented graph $G$ in terms of its $2$-dipath chromatic number $χ_2(G)$, degeneracy $d(G)$, and maximum degree $Δ(G)$. In particular, we show that for all graphs $G$ with $χ_2(G) \leq k$ where $k \geq 2$ and $d(G) \leq t$ where $t \geq \log_2(k)$, $χ_o(G) = 33/10(k t^2 2^t)$. This improves an upper bound of MacGillivray, Raspaud, and Swartz of the form $χ_o(G) \leq 2^{χ_2(G)} -1$ to a polynomial upper bound for many classes of graphs, in particular, those with bounded degeneracy. Additionally, we asymptotically improve bounds for the oriented chromatic number in terms of maximum degree and degeneracy. For instance, we show that $χ_o(G) \leq (2\ln2 +o(1))Δ^2 2^Δ$ for all graphs, and $χ_o(G) \leq (2+o(1))Δd 2^d$ for graphs where degeneracy grows sublinearly in maximum degree. Here the asypmtotics are in $Δ$. The former improves the asymptotics of a results by Kostochka, Sopena, and Zhu \cite{kostochka1997acyclic}, while the latter improves the asymptotics of a result by Aravind and Subramanian \cite{aravind2009forbidden}. Both improvements are by a constant factor.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。