Counting colorings of triangle-free graphs

DOI10.1016/j.jctb.2023.02.004zbMath1516.05060arXiv2109.13376MaRDI QIDQ6038582

Akum Kang, Tyler Brazelton, Ruijia Cao, Anton Bernshteyn

Publication date: 2 May 2023

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2109.13376

zbMATH Keywords

graph coloringrandom regular graphstriangle-free graphsDP-coloringnumber of coloringsRosenfeld counting

Mathematics Subject Classification ID

Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Vertex degrees (05C07)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Sidorenko's conjecture, colorings and independent sets
• Nonrepetitive colouring via entropy compression
• Correspondence coloring and its application to list-coloring planar graphs without cycles of lengths 4 to 8
• On the chromatic number of random regular graphs
• A probabilistic proof of an asymptotic formula for the number of labelled regular graphs
• On the independence and chromatic numbers of random regular graphs
• The list chromatic number of graphs with small clique number
• Information-theoretic thresholds from the cavity method
• Bounding \(\chi\) by a fraction of \(\Delta\) for graphs without large cliques
• Another approach to non-repetitive colorings of graphs of bounded degree
• On the chromatic polynomial and counting DP-colorings of graphs
• A correlation inequality for bipartite graphs
• Acyclic edge-coloring using entropy compression
• A constructive proof of the general lovász local lemma
• Randomized Distributed Edge Coloring via an Extension of the Chernoff--Hoeffding Bounds
• On the average size of independent sets in triangle-free graphs
• Coloring triangle‐free graphs with local list sizes
• The Johansson‐Molloy theorem for DP‐coloring
• Harmonious coloring of uniform hypergraphs
• Graph colouring and the probabilistic method
• The condensation phase transition in random graph coloring

This page was built for publication: Counting colorings of triangle-free graphs