On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees

Chuandong Xu, Shenggui Zhang, Yi Wang

科研成果: 期刊稿件文章同行评审

摘要

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.

源语言英语
页(从-至)939-944
页数6
期刊Information Processing Letters
115
12
DOI
出版状态已出版 - 14 8月 2015

指纹

探究 'On the maximum arc-chromatic number of digraphs with bounded outdegrees or indegrees' 的科研主题。它们共同构成独一无二的指纹。

引用此