Counting colorings of triangle-free graphs (Q6038582)

The Johansson-Molloy theorem states that if \(G\) is a triangle-free graph of maximum degree \(\Delta\), then \[ \chi(G)\leqslant(1+o(1))\frac{\Delta}{\log\Delta} \] [\textit{A. Johansson}, Asymptotic choice number for triangle free graphs. Techn. Rep. 91--95, DIMACS (1996); \textit{M. Molloy}, J. Comb. Theory, Ser. B 134, 264--284 (2019; Zbl 1402.05076)]). In the paper under review, the authors establish a lower bound on the number \(c(G,q)\) of proper \(q\)-colorings of \(G\) when \(q\geqslant(1 + o(1))\Delta/\log\Delta\). More precisely, the authors obtain the following result (Theorem 1.2): For each \(\varepsilon>0\), there is \(\Delta_0\in\mathbb{N}\) such that if \(G\) is a triangle-free graph of maximum degree at most \(\Delta\geq\Delta_0\), then for every \(q\geqslant(1 + \varepsilon)\Delta/\log\Delta\) we have \[ c(G, q)\geqslant\left(1-\frac{1}{q}\right)^m((1-\delta)q)^n, \] where \(n = |V (G)|\), \(m = |E(G)|\), and \(\delta = 4\exp(\Delta/q)/q\). On the other hand, the following result is also true (Theorem 1.3): Let \(\Delta\) and \(q\) be integers. For every sufficiently large \(n\in\mathbb{N}\) such that \(\Delta n\) is even, there exists a triangle-free \(\Delta\)-regular graph \(G\) with \[ c(G, q)\leqslant\left(1-\frac{1}{q}\right)^m((1+\gamma)q)^n, \] where \(n = |V (G)|\), \(m = |E(G)|=\Delta n/2\), and \(\gamma = 2\log n/n\). The authors deduce several corollaries from their results: 1) The result of \textit{F. Iliopoulos}, [LIPIcs -- Leibniz Int. Proc. Inform. 116, Article 44, 20 p. (2018; Zbl 1522.68743)] on the exponential growth of the number of colorings is significantly improved. More precisely, it is proved that if \(G\) is an \(n\)-vertex triangle-free graph of maximum degree at most \(\Delta\), \(\varepsilon>0\), and \(q\geqslant(1+\varepsilon)\Delta/\log\Delta\), then \[ c(G,q)\geqslant\exp\left(\left(1+\frac{\varepsilon}{1+\varepsilon}-o(1)\right)\frac{\log\Delta}{2}n\right). \] 2) The optimal lower bound on the number of independent sets in triangle-free graphs obtained in \textit{E. Davies} et al., [Random Struct. Algorithms 53, No. 1, 59--75 (2018; Zbl 1401.05108)]: If \(G\) is an \(n\)-vertex triangle-free graph of maximum degree at most \(\Delta\), then \[ i(G)\geqslant\exp\left((1-o(1))\frac{\log^2\Delta}{2\Delta}n\right). \] 3) If \(G\) is an \(n\)-vertex triangle-free graph of maximum degree at most \(\Delta\), then \[ c(G,\Delta+1)\geqslant\left(\frac{\Delta}{\sqrt{e}}-O(1)\right)^n. \] At the end of the paper, the authors formulate two unsolved problems. The authors note that an important ingredient of their proof of the main result is the counting method that was recently developed by \textit{M. Rosenfeld}, [Electron. J. Comb. 27, No. 3, Research Paper P3.43, 16 p. (2020; Zbl 1441.05083)].