Acyclic edge-coloring using entropy compression

详细信息    查看全文

• 作者：Louis Esperet^a ; ¹ ; ^{esperet@gmail.com} ; ^{louis.esperet@g-scop.inpg.fr} ; Aline Parreau^b
• 刊名：European Journal of Combinatorics
• 出版年：2013
• 出版时间：August, 2013
• 年：2013
• 卷：34
• 期：6
• 页码：1019-1027
• 全文大小：396 K

文摘

An edge-coloring of a graph is acyclic if it is a proper edge-coloring of and every cycle contains at least three colors. We prove that every graph with maximum degree has an acyclic edge-coloring with at most colors, improving the previous bound of . 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 , where and are the number of vertices and edges of . Such a randomized procedure running in expected polynomial time was only known to exist in the case where at least 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 colors.