TY - JOUR
T1 - On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees
AU - Xu, Chuandong
AU - Zhang, Shenggui
AU - Wang, Yi
N1 - Publisher Copyright:
© 2015 Elsevier B.V. All rights reserved.
PY - 2015/8/14
Y1 - 2015/8/14
N2 - A k-digraph is a digraph in which every vertex has outdegree at most k, and a (k ∨ l)-digraph is a digraph in which every vertex has either outdegree at most k or indegree at most l. The maximum arc-chromatic number of digraphs over the k-digraphs and the (k ∨ l)-digraphs are denoted by Φ(k) and (k,l), respectively. In this paper we first show that Φ(k)=θ(2k)=2t when k=(2t-1t-1) for t ≥ 2, where θ is the function defined by θ(n)=min{t:(t⌊t/2⌋) ≥ n}. Then we prove that (k,k)≤(2k)+1 for k ≥ 1. The corollary of these results proves weaker versions of two conjectures of Bessy et al., i.e., Φ(k+1)≤;Φ(k)+1 holds for almost all k, and (k,k)≤Φ(k)+1 holds when k=(2t-1t-1) for t ≥ 2.
AB - A k-digraph is a digraph in which every vertex has outdegree at most k, and a (k ∨ l)-digraph is a digraph in which every vertex has either outdegree at most k or indegree at most l. The maximum arc-chromatic number of digraphs over the k-digraphs and the (k ∨ l)-digraphs are denoted by Φ(k) and (k,l), respectively. In this paper we first show that Φ(k)=θ(2k)=2t when k=(2t-1t-1) for t ≥ 2, where θ is the function defined by θ(n)=min{t:(t⌊t/2⌋) ≥ n}. Then we prove that (k,k)≤(2k)+1 for k ≥ 1. The corollary of these results proves weaker versions of two conjectures of Bessy et al., i.e., Φ(k+1)≤;Φ(k)+1 holds for almost all k, and (k,k)≤Φ(k)+1 holds when k=(2t-1t-1) for t ≥ 2.
KW - Arc-chromatic number
KW - Combinatorial problems
KW - Digraph
KW - Indegree
KW - Outdegree
UR - http://www.scopus.com/inward/record.url?scp=84939132563&partnerID=8YFLogxK
U2 - 10.1016/j.ipl.2015.07.013
DO - 10.1016/j.ipl.2015.07.013
M3 - 文章
AN - SCOPUS:84939132563
SN - 0020-0190
VL - 115
SP - 939
EP - 944
JO - Information Processing Letters
JF - Information Processing Letters
IS - 12
ER -