Graphs and Matroid Seminar - Cléophée Robin

Title: When all holes have the same length

Abstract: A hole is an induced cycle of length at least 4. For an integer k ≥ 4, we denote by Ck, the class of graphs where every hole has length k. We have defined a new class of graphs named blowup of ℓ-templates whose all holes have length 2ℓ + 1. Using earlier results on other related classes of graphs, we did obtain the following structural theorem :Theorem 1 Let ℓ ≥ 3 be an integer. If G is a graph in C2ℓ+1 then one of the following holds :

— G is a ring of length 2ℓ + 1,

— G is a proper blowup of a twinless odd ℓ-template,

— G has a universal vertex,

— G has a clique cutset.

The classes of perfect graphs and even-hole-free graphs, both exclude holes depending on the parity of their length. For an even k ≥ 6, Ck is a subclass of the class of perfect graphs and for an odd k, Ck is a subclass of even-hole-free graphs. The well-known class of chordal graphs (graphs containing no hole) is trivially included in every Ck Linda Cook and Paul Seymour independently found a similar characterization.