English

运筹学学报 ›› 2015, Vol. 19 ›› Issue (2): 91-98.doi: 10.15960/j.cnki.issn.1007-6093.2015.02.010

• 运筹学 • 上一篇    下一篇

竞赛图弧色数的上界

徐川东,1 张胜贵1,*, 王艺1   

  1. 1. 西北工业大学理学院应用数学系, 西安 710072
  • 收稿日期:2014-04-15 出版日期:2015-06-15 发布日期:2015-06-15
  • 通讯作者: 张胜贵 sgzhang@nwpu.edu.cn

Upper bounds of the arc-chromatic number of tournaments

XU Chuandong1,ZHANG Shenggui1,*,WANG Yi1   

  1. 1. Department of Applied Mathematics, School of Sciences, Northwestern Polytechnical University, Xi'an 710072, China
  • Received:2014-04-15 Online:2015-06-15 Published:2015-06-15

PDF

1129

摘要：

有向图的弧色数指的是对有向图的弧进行着色, 使得所有连贯弧着不同颜色所需要的最少颜色数. 在介绍了一些相关结果的基础上, 通过确定顶点数较少的竞赛图弧色数的最大值, 说明了已有弧色数的上界虽然对一般有向图是紧的, 对竞赛图却是可以改进的.

关键词: 弧着色, 弧色数, 竞赛图

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