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

DOI10.1016/J.JCTB.2017.12.004MaRDI QIDQ2173431zbMATH OpenOpenAlexDBLPWikidataFDO

Authors Emilie Diot, Marko Radovanović, Nicolas Trotignon, Kristina Vušković

Publication date 22 April 2020

Published in Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1504.01862

zbMATH Keywords

2-joinclique cutsetdecompositioninduced subgraphrecognition algorithmstructure theoremTruemper configuration

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

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.

Recommendations

• The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Extremal Theta-free planar graphs
• The prism-free planar graphs and their cycles bases
• On the Maximum Number of Triangles in Wheel-Free Graphs
• scientific article; zbMATH DE number 1047729
• From crossing-free graphs on wheel sets to embracing simplices and polytopes with few vertices

Cites work

• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• A class of three-colorable triangle-free graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Algorithms for Perfectly Contractile Graphs
• Algorithms for Square-3PC(\cdot, \cdot)-Free Berge Graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Cycles and Connectivity in Graphs
• Decomposition by clique separators
• Depth-First Search and Linear Graph Algorithms
• Detecting 2-joins faster
• Detecting a Theta or a Prism
• Detecting wheels
• Edge-colouring and total-colouring chordless graphs
• Even and odd holes in cap-free graphs
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Even-hole-free graphs. I: Decomposition theorem
• Graphs that do not contain a cycle with a node that has at least two neighbors on it
• Graphs with no induced wheel and no induced antiwheel
• Non-separating induced cycles in graphs
• On graphs with no induced subdivision of \(K_4\)
• On rigid circuit graphs
• Recognizing Berge graphs
• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• The strong perfect graph theorem
• The structure of bull-free graphs II and III -- a summary
• The structure of claw-free graphs
• The three-in-a-tree problem
• The world of hereditary graph classes viewed through Truemper configurations
• Universally signable graphs
• Vertex elimination orderings for hereditary graph classes
• Wheel-free planar graphs

Cited in

(14)

• Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs
• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Clique cutsets beyond chordal graphs
• Graphs with polynomially many minimal separators
• The world of hereditary graph classes viewed through Truemper configurations
• Detecting a Theta or a Prism
• The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
• Clique-cutsets beyond chordal graphs
• Finding a shortest even hole in polynomial time
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Isometric path complexity of graphs
• Detecting \(K_{2,3}\) as an induced minor

This page was built for publication: The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2173431)