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

Stéphane Bessy 1 Etienne Birmele 2 Frédéric Havet 3
1 ALGCO - Algorithmes, Graphes et Combinatoire
LIRMM - Laboratoire d'Informatique de Robotique et de Microélectronique de Montpellier
3 MASCOTTE - Algorithms, simulation, combinatorics and optimization for telecommunications
CRISAM - Inria Sophia Antipolis - Méditerranée , COMRED - COMmunications, Réseaux, systèmes Embarqués et Distribués
Abstract : A {\it $k$-digraph} is a digraph in which every vertex has outdegree at most $k$. A {\it $(k\vee l)$-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\vee l)$-digraphs). El-Sahili~\cite{ElS03} 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 $\ds \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$.
Type de document :
Article dans une revue
Journal of Graph Theory, Wiley, 2006, 53 (4), pp.315-332
Liste complète des métadonnées

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00153978
Contributeur : Stephan Thomasse <>
Soumis le : mardi 12 juin 2007 - 14:30:53
Dernière modification le : vendredi 10 février 2017 - 01:11:44

Identifiants

  • HAL Id : lirmm-00153978, version 1

Collections

Citation

Stéphane Bessy, Etienne Birmele, Frédéric Havet. Arc-chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree.. Journal of Graph Theory, Wiley, 2006, 53 (4), pp.315-332. <lirmm-00153978>

Partager

Métriques

Consultations de la notice

202