The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs

DOI10.1002/JGT.22415zbMATH Open1411.05223OpenAlexW2898320738MaRDI QIDQ4632025FDOQ4632025

Authors: Valerio Boncompagni, Kristina Vušković, Marko Radovanović 

Publication date: 25 April 2019

Published in: Journal of Graph Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1002/jgt.22415

Recommendations

• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• The (theta, wheel)-free graphs. II: Structure theorem
• On graphs with no induced subdivision of \(K_4\)
• The (theta, wheel)-free graphs. IV: Induced paths and cycles

zbMATH Keywords

decompositionstructurevertex coloringrecognition algorithmclique cutsets2-amalgamsbisimplicial cutsets

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75)

Cites Work

• Paths, Trees, and Flowers
• Induced subdivisions in \(K_{s,s}\)-free graphs of large average degree
• The ellipsoid method and its consequences in combinatorial optimization
• Perfect graphs
• Title not available (Why is that?)
• Recognizing Berge graphs
• Algorithms for Perfectly Contractile Graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• Alpha-balanced graphs and matrices and GF(3)-representability of matroids
• Universally signable graphs
• Graphs of separability at most 2
• The three-in-a-tree problem
• Algorithms for Square-3PC($\cdot, \cdot$)-Free Berge Graphs
• Vertex elimination orderings for hereditary graph classes
• The world of hereditary graph classes viewed through Truemper configurations
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Detecting wheels

Cited In (5)

• On graphs with no induced subdivision of \(K_4\)
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring

This page was built for publication: The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs

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