When all holes have the same length

2022/03/22 by Horsfield, Jake, Preissmann, Myriam, Robin, Cléophée +3
#05C75 #Combinatorics (math.CO) #FOS: Mathematics #G.2.2

paper · doi:10.48550/arxiv.2203.11571

Abstract

For every integer ℓ ≥ 7, we give a structural description of the class of graphs whose chordless cycles of length at least 4 all have length ℓ.

Related

• Induced subgraphs of graphs with large chromatic number. IV. Consecutive holes
• On the Erdős-Pósa property for long holes in C₄-free graphs
• Detecting a long even hole
• On recognition algorithms and structure of graphs with restricted induced cycles
• Erdős-Pósa property of chordless cycles and its applications