{'fraction_non_alphanumeric': 0.061366806136680614, 'fraction_numerical': 0.05299860529986053, 'mean_word_length': 3.8843537414965987, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Randomly coloring graphs with lower bounds on girth and maximum degree

We consider the problem of generating a random q‐coloring of a graph G = (V, E). We consider the simple Glauber Dynamics chain. We show that if the maximum degree Δ > c1ln n and the girth g > c2ln Δ (n = |V|) for sufficiently large c1, c2, then this chain mixes rapidly provided q/Δ > β, where β ≈ 1.763 is the root of β = e1/β. For this class of graphs, this beats the 11Δ/6 bound of Vigoda E. Vigoda, Improved bounds for sampling colorings, Proc 40th Annu IEEE Symp Foundations of Computer Science, 1999, pp. 51–59 for general graphs. We extend the result to random graphs. © 2003 Wiley Periodicals, Inc. Random Struct. Alg., 23: 167–179, 2003