Title: When all holes have the same length
| Speaker: | Cléophée Robin |
| Affiliation: | University of Waterloo |
| Location: | MC 6029 |
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.