Arc-chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree
✍ Scribed by S. Bessy; F. Havet; E. Birmelé
- Book ID
- 102344571
- Publisher
- John Wiley and Sons
- Year
- 2006
- Tongue
- English
- Weight
- 221 KB
- Volume
- 53
- Category
- Article
- ISSN
- 0364-9024
No coin nor oath required. For personal study only.
✦ Synopsis
Abstract
A k‐digraph is a digraph in which every vertex has outdegree at most k. A $(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 Φ (k) (resp. $\Phi^{\vee}(k, l)$) of the arc‐chromatic number over the k‐digraphs (resp. $(k \vee l)$‐digraphs). El‐Sahili [3] showed that $\Phi^{\vee}(k, k) \leq 2 k + 1$. After giving a simple proof of this result, we show some better bounds. We show $\max{\log(2 k + 3), \theta(k + 1)}\leq \Phi(k) \leq \theta(2 k)$ and $\max{\log(2 k + 2 l + 4), \theta(k + 1), \theta(l + 1)}\leq \Phi^{\vee}(k, l)\leq \theta (2 k + 2 l)$ where θ is the function defined by $\theta({{k}}) =\min {{{s}} : {{{s}} \choose \left\lceil {{{{s}}}\over{{\rm{2}}}} \right\rceil} \geq {{k}} }$. We then study in more detail properties of Φ and $\Phi^{\vee}$. Finally, we give the exact values of $\Phi({{k}})$ and $\Phi^{\vee}({{k}},{{l}})$ for ${{l}} \leq {{k}} \leq {\rm{3}}$. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 315–332, 2006