Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2023

Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring

Résumé

Let $D=(V,A)$ be a digraph. We define $\Delta_{\max}(D)$ as the maximum of $\{ \max(d^+(v),d^-(v)) \mid v \in V \}$ and $\Delta_{\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 $\Delta_{\min}(D) + 1$. In this work, we prove that every digraph $D$ which has dichromatic number exactly $\Delta_{\min}(D) + 1$ must contain the directed join of $\overleftrightarrow{K_r}$ and $\overleftrightarrow{K_s}$ for some $r,s$ such that $r+s = \Delta_{\min}(D) + 1$, except if $\Delta_{\min}(D) = 2$ in which case $D$ must contain a digon. In particular, every oriented graph $\vec{G}$ with $\Delta_{\min}(\vec{G}) \geq 2$ has dichromatic number at most $\Delta_{\min}(\vec{G})$. Let $\vec{G}$ be an oriented graph of order $n$ such that $\Delta_{\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\Delta_{\min}(\vec{G})n$ when $k\geq \Delta_{\min}(\vec{G}) + 1$. We then extend a theorem of Feghali, Johnson and Paulusma to digraphs. We prove that, for every digraph $D$ with $\Delta_{\max}(D) = \Delta \geq 3$ and every $k\geq \Delta +1$, the $k$-dicolouring graph of $D$ consists of isolated vertices and at most one further component that has diameter at most $c_{\Delta}n^2$, where $c_{\Delta} = O(\Delta^2)$ is a constant depending only on $\Delta$.
Fichier principal
Vignette du fichier
2301.04881 (213.76 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte

Dates et versions

hal-04204446 , version 1 (12-12-2023)

Identifiants

Citer

Lucas Picasarri-Arrieta. Strengthening the Directed Brooks' Theorem for oriented graphs and consequences on digraph redicolouring. Eurocomb 2023 - 12th European Conference on Combinatorics, Graph Theory and Applications, Aug 2023, Prague, Czech Republic. pp.760-765, ⟨10.5817/CZ.MUNI.EUROCOMB23-105⟩. ⟨hal-04204446⟩
35 Consultations
2 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More