




















Let $D=(V,A)$ be a digraph. We define $Δ_{\max}(D)$ as the maximum of $\{ \max(d^+(v),d^-(v)) \mid v \in V \}$ and $Δ_{\min}(D)$ as the maximum of $\{ \min(d^+(v),d^-(v)) \mid v \in V \}$. It is known that the dichromatic number of $D$ is at most $Δ_{\min}(D) + 1$. In this work, we prove that every digraph $D$ which has dichromatic number exactly $Δ_{\min}(D) + 1$ must contain the directed join of $\overleftrightarrow{K_r}$ and $\overleftrightarrow{K_s}$ for some $r,s$ such that $r+s = Δ_{\min}(D) + 1$, except if $Δ_{\min}(D) = 2$ in which case $D$ must contain a digon. In particular, every oriented graph $\vec{G}$ with $Δ_{\min}(\vec{G}) \geq 2$ has dichromatic number at most $Δ_{\min}(\vec{G})$. Let $\vec{G}$ be an oriented graph of order $n$ such that $Δ_{\min}(\vec{G}) \leq 1$. Given two 2-dicolourings of $\vec{G}$, we show that we can transform one into the other in at most $n$ steps, by recolouring one vertex at each step while maintaining a dicolouring at any step. Furthermore, we prove that, for every oriented graph $\vec{G}$ on $n$ vertices, the distance between two $k$-dicolourings is at most $2Δ_{\min}(\vec{G})n$ when $k\geq Δ_{\min}(\vec{G}) + 1$. We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every digraph $D$ with $Δ_{\max}(D) = Δ\geq 3$ and every $k\geq Δ+1$, the $k$-dicolouring graph of $D$ consists of isolated vertices and at most one further component that has diameter at most $c_Δn^2$, where $c_Δ = O(Δ^2)$ is a constant depending only on $Δ$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。