(Theta, triangle)-free and (even hole, K_4)-free graphs. Part 1 : Layered wheels
share
We present a construction called layered wheel. Layered wheels are graphs of arbitrarily large treewidth and girth. They might be an outcome for a possible theorem characterizing graphs with large treewidth in term of their induced subgraphs (while such a characterization is well understood in term of minors). They also provide examples of graphs of large treewidth and large rankwidth in well studied classes, such as (theta, triangle)-free graphs and even-hole-free graphs with no K_4 (where a hole is a chordless cycle of length at least 4, a theta is a graph made of three internally vertex disjoint paths of length at least 2 linking two vertices, and K_4 is the complete graph on 4 vertices).
READ FULL TEXT