A 2016 conjecture of Brewster, McGuinness, Moore, and Noel asserts that for $k \ge 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 four cycles of length $0 \bmod 3$, and that $K_4$ 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 \ne 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.
@article{10_37236_12623,
author = {Sean Kim and Michael Picollelli},
title = {4-Chromatic graphs have at least four cycles of length 0 mod 3},
journal = {The electronic journal of combinatorics},
year = {2024},
volume = {31},
number = {2},
doi = {10.37236/12623},
zbl = {1543.05054},
url = {http://geodesic.mathdoc.fr/articles/10.37236/12623/}
}
TY - JOUR
AU - Sean Kim
AU - Michael Picollelli
TI - 4-Chromatic graphs have at least four cycles of length 0 mod 3
JO - The electronic journal of combinatorics
PY - 2024
VL - 31
IS - 2
UR - http://geodesic.mathdoc.fr/articles/10.37236/12623/
DO - 10.37236/12623
ID - 10_37236_12623
ER -
%0 Journal Article
%A Sean Kim
%A Michael Picollelli
%T 4-Chromatic graphs have at least four cycles of length 0 mod 3
%J The electronic journal of combinatorics
%D 2024
%V 31
%N 2
%U http://geodesic.mathdoc.fr/articles/10.37236/12623/
%R 10.37236/12623
%F 10_37236_12623
Sean Kim; Michael Picollelli. 4-Chromatic graphs have at least four cycles of length 0 mod 3. The electronic journal of combinatorics, Tome 31 (2024) no. 2. doi: 10.37236/12623
