Generalized acyclic edge colorings via entropy compression
Generalized acyclic edge colorings via entropy compression
复制标题
通过熵压缩的广义非循环边缘着色
DOI：
10.1007/s10878-017-0244-8
复制
发表时间：
2018-01
影响因子：
1
通讯作者：
Wu Jianliang
中科院分区：
文献类型：
--
作者：
Ding Laihao;Wang Guanghui;Wu Jianliang
图G的无圈边染色是一种正常边染色，使得任意圈C至少有个颜色。G的非循环边着色所需的最少颜色数称为G的非循环边色数或非循环色指数，表示为。本文研究了图的-非循环边色数，证明了。我们还证明了，当是偶数时，这是渐近最优的。此外，我们还研究了无圈边色数随围长的增加而变化的规律。本文证明了对任意围长至少为G的图G，我们的方法是基于熵压缩方法。
Anr-acyclic edge coloring of a graphGis a proper edge coloring such that any cycleChas at leastcolors. The least number of colors needed for anr-acyclic edge coloring ofGis called ther-acyclic edge chromatic number or ther-acyclic chromatic index ofG, denoted by. In this paper, we study ther-acyclic edge chromatic number withand prove that. We also prove that whenris even,, which is asymptotically optimal. In addition, we investigate how ther-acyclic edge chromatic number performs as the girth increases. It is proved in this paper that for every graphGwith girth at least,holds. Our approach is based on the entropy compression method.
登录
查看更多内容
影响因子：
0.9
作者：
S. Gerke;Catherine S. Greenhill;N. Wormald
通讯作者：
S. Gerke;Catherine S. Greenhill;N. Wormald
DOI：
10.1016/j.ejc.2013.02.007
发表时间：
2012-06
期刊：
Eur. J. Comb.
影响因子：
--
作者：
Louis Esperet;Aline Parreau
通讯作者：
Louis Esperet;Aline Parreau
DOI：
10.1016/j.disc.2006.09.004
发表时间：
2007-06
期刊：
Discret. Math.
影响因子：
--
作者：
S. Gerke;Melanie Raemy
通讯作者：
S. Gerke;Melanie Raemy
影响因子：
0.9
作者：
Péter Komjáth;S. Shelah
通讯作者：
Péter Komjáth;S. Shelah
DOI：
--
发表时间：
2006
期刊：
--
影响因子：
--
作者：
N. Alon;C. McDiarmid
通讯作者：
N. Alon;C. McDiarmid