中文

Operations Research Transactions >

2015 , Vol. 19 >Issue 2: 91 - 98

DOI: https://doi.org/10.15960/j.cnki.issn.1007-6093.2015.02.010

Upper bounds of the arc-chromatic number of tournaments

Expand
  • 1. Department of Applied Mathematics, School of Sciences, Northwestern Polytechnical University, Xi'an 710072, China

Received date: 2014-04-15

  Online published: 2015-06-15

Fold

Abstract

The arc-chromatic number of a digraph is the smallest number of colors required in an arc-coloring such that no two consecutive arcs get the same color. We first introduce some results on the arc-coloring of digraphs, then give a discussion about the upper bound of the arc-chromatic number of tournaments. By determining the maximum arc-chromatic number of tournaments with order at most $8$, we show that although the upper bound of the arc-chromatic number of general digraphs is tight, it is not tight for tournaments.

Key words： arc-coloring; arc-chromatic number; tournaments

Cite this article

XU Chuandong,ZHANG Shenggui,WANG Yi . Upper bounds of the arc-chromatic number of tournaments[J]. Operations Research Transactions, 2015 , 19(2) : 91 -98 . DOI: 10.15960/j.cnki.issn.1007-6093.2015.02.010

References


Bondy J A, Murty U S R. Graph Theory [M]. New York: Springer,  2008.

Alon N, Bollobas B, Gyarfas A, et al. Maximum directed cuts in acyclic digraphs [J]. Journal of Graph Theory, 2007, 55: 1-13.

Bai Y, Li B, Zhang S. Covering the edges of digraphs in \mathcal{D(3,3)} and \mathcal{D(4,4)} with directed cuts [J]. Discrete Mathematics, 2012, 312: 1596-1601.

Xu C, Zhang S, Lu Y. Covering digraphs with small indegrees or outdegrees by directed cuts [J]. Discrete Mathematics, 2013, 313: 1648-1654.

Harner C C, Entringer R C. Arc coloring of digraphs [J]. Journal of Combinatorial Theory: Series B, 1972, 13: 219-225.
 
Poljak S, R\"odl V. On the arc-chromatic number of a digraph [J]. Journal of Combinatorial Theory : Series B, 1981, 31: 190-198.

Bessy S, Havet F, Birmele E. Arc-chromatic number of digraphs in which every vertex has bounded outdegree or bounded indegree [J]. Journal of Graph Theory, 2006, 53: 315-332.

 
Options
Outlines

/

〈 〉