WorksMathematics
Minimum degree thresholds for even cycle residues
Abstract
Dean's conjecture asserts that, for every integer , every graph of minimum degree at least has a cycle whose length is divisible by . This degree bound is best possible for odd . For every integer , we prove that every graph of minimum degree at least has a cycle whose length is congruent to modulo for every even . Consequently, is the sharp minimum degree threshold for a cycle whose length is divisible by . For bipartite graphs, we prove that minimum degree at least guarantees the same residue classes for every , and we characterize their end-blocks when no cycle has length congruent to modulo . The bipartite degree bound is also sharp, and the exclusion of residue is necessary even for connected graphs of arbitrarily large order.