Name
Title | ||
|---|---|---|
Arc-chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree |
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 &thetas; 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 |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1002/jgt.v53:4 | Journal of Graph Theory |
Keywords | Field | DocType |
function theory,digraph | Combinatorics,Function (mathematics),Vertex (geometry),Mathematics,Bounded function | Journal |
Volume | Issue | ISSN |
53 | 4 | 0364-9024 |
Citations | PageRank | References |
5 | 0.52 | 2 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Stéphane Bessy | 1 | 117 | 19.68 |
| Frédéric Havet | 2 | 433 | 55.15 |
| Etienne Birmelé | 3 | 57 | 7.11 |