Acyclic edge-coloring using entropy compression
Acyclic edge-coloring using entropy compression
复制标题
DOI：
10.1016/j.ejc.2013.02.007
复制
发表时间：
2012-06
期刊：
影响因子：
--
通讯作者：
Louis Esperet;Aline Parreau
中科院分区：
文献类型：
--
作者：
Louis Esperet;Aline Parreau
图G的一个边染色是无圈的，如果它是G的一个真边染色，且每个圈至少包含三种颜色。我们证明了每一个度为Δ的图都有最多4个Δ−4色的无圈边染色，改进了之前的界为Δ 9.62（Δ−1）λ。我们的约束结果从一个非常简单的随机过程，使用所谓的熵压缩方法的分析。我们证明了该过程的期望运行时间是O（mnΔ2logΔ），其中n和m是G的顶点数和边数.这种在预期多项式时间内运行的随机化过程仅在至少16种Δ颜色可用的情况下存在。我们在这里的目的是做一个教学教程如何使用这些想法来分析广泛的图着色问题。作为应用，我们还证明了每个度为Δ的图都有22个Δ3/2+Δ色的星星染色.
An edge-coloring of a graph G is acyclic if it is a proper edge-coloring of G and every cycle contains at least three colors. We prove that every graph with maximum degree Δ has an acyclic edge-coloring with at most 4Δ−4 colors, improving the previous bound of ⌈9.62(Δ−1)⌉. Our bound results from the analysis of a very simple randomized procedure using the so-called entropy compression method. We show that the expected running time of the procedure is O(mnΔ2logΔ), where n and m are the number of vertices and edges of G. Such a randomized procedure running in expected polynomial time was only known to exist in the case where at least 16Δ colors were available. Our aim here is to make a pedagogic tutorial on how to use these ideas to analyze a broad range of graph coloring problems. As an application, we also show that every graph with maximum degree Δ has a star coloring with 22Δ3/2+Δ colors.