The generalized acyclic edge chromatic number of random regular graphs
The generalized acyclic edge chromatic number of random regular graphs
复制标题
DOI：
10.1002/jgt.20167
复制
发表时间：
2006-10
影响因子：
0.9
通讯作者：
S. Gerke;Catherine S. Greenhill;N. Wormald
中科院分区：
文献类型：
--
作者：
S. Gerke;Catherine S. Greenhill;N. Wormald
图的 r-非循环边色数定义为产生图的边着色所需的最小颜色数，使得相邻边接收不同的颜色并且每个循环 C 至少具有 min(|C|, r) 种颜色。我们证明，对于所有常数 r ≥ 4 和 d ≥ 2，(r − 2)d 几乎可以肯定（a.a.s.）是随机 d-正则图的 r-无环边缘色数的上限。 © 2006 Wiley periodicals, Inc. J Graph Theory 53: 101–125, 2006
The r‐acyclic edge chromatic number of a graph is defined to be the minimum number of colors required to produce an edge coloring of the graph such that adjacent edges receive different colors and every cycle C has at least min(|C|, r) colors. We show that (r − 2)d is asymptotically almost surely (a.a.s.) an upper bound on the r‐acyclic edge chromatic number of a random d‐regular graph, for all constants r ≥ 4 and d ≥ 2. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 101–125, 2006