2022/06/29 by Bernstine, Aya, Linial, Nati
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2206.14638
We offer a new, gradual approach to the largest girth problem for cubic graphs. It is easily observed that the largest possible girth of all n-vertex cubic graphs is attained by a 2-connected graph G=(V,E). By Petersen's graph theorem, E is the disjoint union of a 2-factor and a perfect matching M. We refer to the edges of M as chords and classify the cycles in G by their number of chords. We define γk(n) to be the largest integer g such that every cubic n-vertex graph with a given perfect matching M has a cycle of length at most g with at most k chords. Here we determine this function up to small additive constant for k= 1, 2 and up to a small multiplicative constant for larger k.