首页 | 本学科首页   官方微博 | 高级检索  
     


The Johansson‐Molloy theorem for DP‐coloring
Authors:Anton Bernshteyn
Abstract:The aim of this note is twofold. On the one hand, we present a streamlined version of Molloy's new proof of the bound urn:x-wiley:rsa:media:rsa20811:rsa20811-math-0001 for triangle‐free graphs G, avoiding the technicalities of the entropy compression method and only using the usual “lopsided” Lovász Local Lemma (albeit in a somewhat unusual setting). On the other hand, we extend Molloy's result to DP‐coloring (also known as correspondence coloring), a generalization of list coloring introduced recently by Dvo?ák and Postle.
Keywords:Graph coloring  list coloring  DP‐coloring  triangle‐free graphs  Local Lemma  entropy compression
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号