14:00
15:00

Exposé en anglais / Talk in english

A simple greedy procedure shows that the chromatic number $\chi(G)$ of a graph $G$ is upper bounded by $\Delta(G)+1$. In 1998, Reed conjectured that, in fact, $\chi(G)$ can be bounded halfway between $\Delta(G)+1$ and $\omega(G)$. As a partial result, he proved the existence of $\epsilon >0$ such that $\chi(G) \leq \lceil (1-\epsilon) (\Delta(G)+1) + \epsilon \omega(G) \rceil$, thus showing that $\chi(G)$ is indeed bounded by a convex combination of $\Delta(G)+1$ and $\omega(G)$.

In this talk, we will explore an analogous question for digraphs, where the chromatic number, the maximum degree, and the clique number of a graph are replaced respectively by the dichromatic number, the maximum geometric mean, and the biclique number of a digraph. We prove the analogue of Reed’s result, which also implies an independent result obtained by Harutyunyan and Mohar when restricted to oriented graphs.

Joint work with Ken-ichi Kawarabayashi.
Arxiv: https://arxiv.org/abs/2407.05827

[Lucas Picasarri-Arrietta] (NII, Tokyo)

Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]

Remarks / Remarques

Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .

LaBRI/178