Counting colorings of triangle-free graphs
Counting colorings of triangle-free graphs
复制标题
DOI：
10.1016/j.jctb.2023.02.004
复制
发表时间：
2021-09
期刊：
影响因子：
--
通讯作者：
Anton Bernshteyn;Tyler Brazelton;Ruijia Cao;Akum S. Kang
中科院分区：
文献类型：
--
作者：
Anton Bernshteyn;Tyler Brazelton;Ruijia Cao;Akum S. Kang
根据Johansson的一个定理，对于泛常数C> 0，每个最大度为Δ的无三角形图G的色数至多为（C+ o（1））Δ/log <$Δ.使用熵压缩方法，莫洛伊证明了人们实际上可以取C= 1。这里我们证明了对任意q <$（1+ o（1））Δ/log <$Δ，G的真q-染色数c（G，q）满足c（G，q）<$（1− 1 q）m（（1− o（1））q）n，其中n=| V（G）|和m=| E（G）|.除了o（1）项之外，这个下界是最好的，正如随机Δ-正则图所证明的那样。当q=（1+ o（1））Δ/log <$Δ时，我们的结果得到不等式c（G，q）<$exp <$（（1− o（1））log <$Δ 2 n），它改进了Iliopoulos的早期界，并得到了指数中常数因子的最佳值。此外，这个结果暗示了G中独立集个数的最优下界，这是由Davies，Jenssen，Perkins和Roberts提出的。在我们的证明中，一个重要的组成部分是Rosenfeld最近开发的计数方法。作为一个副产品，我们得到了一个替代的证明莫洛伊的界限χ（G）<$（1+ o（1））Δ/log <$Δ使用罗森菲尔德的方法代替熵压缩（莫洛伊定理的其他证明使用罗森菲尔德的技术是由赫尔利和皮罗特和Martinsson独立）。
By a theorem of Johansson, every triangle-free graph G of maximum degree Δ has chromatic number at most (C+ o (1)) Δ/log Δ for some universal constant C> 0. Using the entropy compression method, Molloy proved that one can in fact take C= 1. Here we show that for every q⩾(1+ o (1)) Δ/log Δ, the number c (G, q) of proper q-colorings of G satisfies c (G, q)⩾(1− 1 q) m ((1− o (1)) q) n, where n=| V (G)| and m=| E (G)|. Except for the o (1) term, this lower bound is best possible as witnessed by random Δ-regular graphs. When q=(1+ o (1)) Δ/log Δ, our result yields the inequality c (G, q)⩾ exp((1− o (1)) log Δ 2 n), which improves an earlier bound of Iliopoulos and yields the optimal value for the constant factor in the exponent. Furthermore, this result implies the optimal lower bound on the number of independent sets in G due to Davies, Jenssen, Perkins, and Roberts. An important ingredient in our proof is the counting method that was recently developed by Rosenfeld. As a byproduct, we obtain an alternative proof of Molloy's bound χ (G)⩽(1+ o (1)) Δ/log Δ using Rosenfeld's method in place of entropy compression (other proofs of Molloy's theorem using Rosenfeld's technique were given independently by Hurley and Pirot and Martinsson).