An analogue of Reed's conjecture for digraphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866916919614898176 |
|---|---|
| author | Kawarabayashi, Ken-ichi Picasarri-Arrieta, Lucas |
| author_facet | Kawarabayashi, Ken-ichi Picasarri-Arrieta, Lucas |
| contents | Reed in 1998 conjectured that every graph $G$ satisfies $χ(G) \leq \lceil \frac{Δ(G)+1+ω(G)}{2} \rceil$. As a partial result, he proved the existence of $\varepsilon > 0$ for which every graph $G$ satisfies $χ(G) \leq \lceil (1-\varepsilon)(Δ(G)+1)+\varepsilonω(G) \rceil$. We propose an analogue conjecture for digraphs. Given a digraph $D$, we denote by $\vecχ(D)$ the dichromatic number of $D$, which is the minimum number of colours needed to partition $D$ into acyclic induced subdigraphs. We let $\overleftrightarrowω(D)$ denote the size of the largest biclique (a set of vertices inducing a complete digraph) of $D$ and $\tildeΔ(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We conjecture that every digraph $D$ satisfies $\vecχ(D) \leq \lceil \frac{\tildeΔ(D)+1+\overleftrightarrowω(D)}{2} \rceil$, which if true implies Reed's conjecture. As a partial result, we prove the existence of $\varepsilon >0$ for which every digraph $D$ satisfies $\vecχ(D) \leq \lceil (1-\varepsilon)(\tildeΔ(D)+1)+\varepsilon\overleftrightarrowω(D) \rceil$. This implies both Reed's result and an independent result of Harutyunyan and Mohar for oriented graphs.
To obtain this upper bound on $\vecχ$, we prove that every digraph $D$ with $\overleftrightarrowω(D) > \frac{2}{3}(Δ_{\max}(D)+1)$, where $Δ_{\max}(D) = \max_{v\in V(D)} \max(d^+(v),d^-(v))$, admits an acyclic set of vertices intersecting each biclique of $D$, which generalises a result of King.
We finally give a short proof that all oriented graphs $D$ satisfy $\vecχ(D) \leq \frac{\sqrt{2}}{2} \TildeΔ(D) + 2$, improving on a result of Golowich. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_05827 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An analogue of Reed's conjecture for digraphs Kawarabayashi, Ken-ichi Picasarri-Arrieta, Lucas Combinatorics Discrete Mathematics Reed in 1998 conjectured that every graph $G$ satisfies $χ(G) \leq \lceil \frac{Δ(G)+1+ω(G)}{2} \rceil$. As a partial result, he proved the existence of $\varepsilon > 0$ for which every graph $G$ satisfies $χ(G) \leq \lceil (1-\varepsilon)(Δ(G)+1)+\varepsilonω(G) \rceil$. We propose an analogue conjecture for digraphs. Given a digraph $D$, we denote by $\vecχ(D)$ the dichromatic number of $D$, which is the minimum number of colours needed to partition $D$ into acyclic induced subdigraphs. We let $\overleftrightarrowω(D)$ denote the size of the largest biclique (a set of vertices inducing a complete digraph) of $D$ and $\tildeΔ(D) = \max_{v\in V(D)} \sqrt{d^+(v) \cdot d^-(v)}$. We conjecture that every digraph $D$ satisfies $\vecχ(D) \leq \lceil \frac{\tildeΔ(D)+1+\overleftrightarrowω(D)}{2} \rceil$, which if true implies Reed's conjecture. As a partial result, we prove the existence of $\varepsilon >0$ for which every digraph $D$ satisfies $\vecχ(D) \leq \lceil (1-\varepsilon)(\tildeΔ(D)+1)+\varepsilon\overleftrightarrowω(D) \rceil$. This implies both Reed's result and an independent result of Harutyunyan and Mohar for oriented graphs. To obtain this upper bound on $\vecχ$, we prove that every digraph $D$ with $\overleftrightarrowω(D) > \frac{2}{3}(Δ_{\max}(D)+1)$, where $Δ_{\max}(D) = \max_{v\in V(D)} \max(d^+(v),d^-(v))$, admits an acyclic set of vertices intersecting each biclique of $D$, which generalises a result of King. We finally give a short proof that all oriented graphs $D$ satisfy $\vecχ(D) \leq \frac{\sqrt{2}}{2} \TildeΔ(D) + 2$, improving on a result of Golowich. |
| title | An analogue of Reed's conjecture for digraphs |
| topic | Combinatorics Discrete Mathematics |
| url | https://arxiv.org/abs/2407.05827 |