The (theta, wheel)-free graphs Part I: only-prism and only-pyramid graphs

Abstract

Truemper configurations are four types of graphs (namely thetas, wheels, prisms and pyramids) that play an important role in the proof of several decomposition theorems for hereditary graph classes. In this paper, we prove two structure theorems: one for graphs with no thetas, wheels and prisms as induced subgraphs, and one for graphs with no thetas, wheels and pyramids as induced subgraphs. A consequence is a polynomial time recognition algorithms for these two classes. In Part II of this series we generalize these results to graphs with no thetas and wheels as induced subgraphs, and in Parts III and IV, using the obtained structure, we solve several optimization problems for these graphs.

References in corpus (8)

• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Algorithms for perfectly contractile graphs
• On graphs with no induced subdivision of $K_4$
• Edge-colouring and total-colouring chordless graphs
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Algorithms for square-$3PC(\cdot ,\cdot )$-free Berge graphs
• Detecting wheels
• Wheel-free planar graphs

Cited by in corpus (5)

• The (theta, wheel)-free graphs Part IV: induced paths and cycles
• (Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 1 : Layered wheels
• Finding a Shortest Even Hole in Polynomial Time
• Isometric path complexity of graphs
• Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs