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

DOI10.1016/j.jctb.2017.12.004zbMath1437.05194arXiv1504.01862OpenAlexW2951002739WikidataQ59885194 ScholiaQ59885194MaRDI QIDQ2173431

Marko Radovanović, Nicolas Trotignon, Emilie Diot, 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

decompositioninduced subgraphstructure theorem2-joinrecognition algorithmclique cutsetTruemper 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)

Related Items

The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring ⋮ Finding a shortest even hole in polynomial time ⋮ (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ The structure of (theta, pyramid, 1‐wheel, 3‐wheel)‐free graphs ⋮ Minimal induced subgraphs of the class of 2-connected non-Hamiltonian wheel-free graphs

Cites Work

• Unnamed Item
• Edge-colouring and total-colouring chordless graphs
• On graphs with no induced subdivision of \(K_4\)
• The three-in-a-tree problem
• The structure of bull-free graphs II and III -- a summary
• On rigid circuit graphs
• The strong perfect graph theorem
• Even-hole-free graphs that do not contain diamonds: A structure theorem and its consequences
• Decomposition by clique separators
• Non-separating induced cycles in graphs
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Universally signable 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
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Wheel-free planar graphs
• Detecting 2-joins faster
• Recognizing Berge graphs
• Vertex elimination orderings for hereditary graph classes
• Even-hole-free graphs part I: Decomposition theorem
• Detecting wheels
• The world of hereditary graph classes viewed through Truemper configurations
• Detecting a Theta or a Prism
• Algorithms for Square-3PC($\cdot, \cdot$)-Free Berge Graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Even and odd holes in cap-free graphs
• Graphs That Do Not Contain a Cycle with a Node That Has at Least Two Neighbors on It
• A Class of Three‐Colorable Triangle‐Free Graphs
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Graphs with no induced wheel and no induced antiwheel
• Algorithms for Perfectly Contractile Graphs
• Cycles and Connectivity in Graphs
• Depth-First Search and Linear Graph Algorithms