4-Chromatic Graphs Have At Least 4 Cycles of Length 0 \bmod 3

2023/12/10 by Kim, Sean, Picollelli, Michael E.
#05C15 #05C38 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2312.05945

Abstract

A 2018 conjecture of Brewster, McGuinness, Moore, and Noel asserts that for k ≥ 3, if a graph has chromatic number greater than k, then it contains at least as many cycles of length 0 \bmod k as the complete graph on k+1 vertices. Our main result confirms this in the k=3 case by showing every 4-critical graph contains at least 4 cycles of length 0 \bmod 3, and that K₄ is the unique such graph achieving the minimum. We make progress on the general conjecture as well, showing that (k+1)-critical graphs with minimum degree k have at least as many cycles of length 0\bmod r as K_k+1, provided k+1 ≠ 0 \bmod r. We also show that K_k+1 uniquely minimizes the number of cycles of length 1\bmod k among all (k+1)-critical graphs, strengthening a recent result of Moore and West and extending it to the k=3 case.

Related

• A note on cycle lengths in graphs of chromatic number five and six
• Cycle lengths and chords under chromatic and degree constraints
• Counting critical subgraphs in k-critical graphs
• On the maximum number of edges in k-critical graphs
• Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3