Abstract:The first major contribution of this work is proving that the oriented relative clique number of oriented triangle-free planar graphs is $10$, which completely answers and closes an open problem posed by Sopena (Discrete Mathematics 2016) in the most recent survey on oriented colorings. The second major contribution of the paper is to prove that if all oriented triangle-free planar graphs admit a homomorphism to a particular oriented graph $\overrightarrow{T}$, then its underlying graph $T$ must have minimum degree at least $10$. This result implies that, for the family of oriented triangle-free planar graphs, the lower bounds of the parameters oriented chromatic number, pushable chromatic number, $2$-dipath $L(p,1)$-labeling span, and oriented $L(p,1)$-labeling span are at least $11$, $6$, $p+8$, and $2p+8$, respectively, where $p \geq 1$. That is, we are able to obtain improved lower bounds of a number of other parameters restricted to the family of oriented triangle-free planar graphs using our second major contribution.
From: Soura Sena Das [view email]
[v1]
Mon, 22 Aug 2022 10:13:48 UTC (16 KB)
[v2]
Fri, 3 Jul 2026 06:56:45 UTC (38 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。