Skip to Main content Skip to Navigation
Reports

Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree

Stéphane Bessy 1 Etienne Birmelé 2 Frédéric Havet 1
1 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , Laboratoire I3S - COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A $k$-digraph is a digraph in which every vertex has outdegree at most $k$. A $(k\veel)$-digraph is a digraph in which a vertex has either outdegree at most $k$ or indegree at most $l$. Motivated by function theory, we study the maximum value $\Phi(k)$ (resp. $\Phi^\vee(k,l)$ of the arc-chromatic number over the $k$-digraphs (resp. $(k\veel)$-digraphs). El-Sahili showed that $\Phi^{\vee}(k,k)\leq 2k+1$. After giving a simple proof of this result, we show some better bounds. We show $\max\{\log(2k+3), \theta(k+1)\}\leq \Phi(k)\leq \theta(2k)$ and $\max\{\log(2k+2l+4), \theta(k+1), \theta(l+1)\}\leq \Phi^{\vee}(k,l)\leq \theta(2k+2l)$ where $\theta$ is the function defined by $\theta(k)=\min\{s : {s\choose \left\lceil \frac{s}{2}\right\rceil}\geq k\}$. We then study in more details properties of $\Phi$ and $\Phi^{\vee}$. Finally, we give the exact values of $\Phi(k)$ and $\Phi^{\vee}(k,l)$ for $l\leq k\leq 3$.
Document type :
Reports
Complete list of metadata

Cited literature [1 references]  Display  Hide  Download

https://hal.inria.fr/inria-00070639
Contributor : Rapport de Recherche Inria <>
Submitted on : Friday, May 19, 2006 - 9:05:46 PM
Last modification on : Wednesday, October 14, 2020 - 4:23:43 AM
Long-term archiving on: : Sunday, April 4, 2010 - 9:37:53 PM

Identifiers

  • HAL Id : inria-00070639, version 1

Citation

Stéphane Bessy, Etienne Birmelé, Frédéric Havet. Arc-chromatic number of digraphs in which each vertex has bounded outdegree or bounded indegree. [Research Report] RR-5364, INRIA. 2004, pp.20. ⟨inria-00070639⟩

Share

Metrics

Record views

319

Files downloads

208