The (theta, wheel)-free graphs. IV: Induced paths and cycles

DOI10.1016/J.JCTB.2020.06.002zbMATH Open1457.05090arXiv1912.00516OpenAlexW3041491102MaRDI QIDQ2221936FDOQ2221936

Authors: Marko Radovanović, Nicolas Trotignon, Kristina Vušković 

Publication date: 3 February 2021

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

Abstract: A hole in a graph is a chordless cycle of length at least 4. A theta is a graph formed by three internally vertex-disjoint paths of length at least 2 between the same pair of distinct vertices. A wheel is a graph formed by a hole and a node that has at least 3 neighbors in the hole. In this series of papers we study the class of graphs that do not contain as an induced subgraph a theta nor a wheel. In Part II of the series we prove a decomposition theorem for this class, that uses clique cutsets and 2-joins. In this paper we use this decomposition theorem to solve several problems related to finding induced paths and cycles in our class.

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

Recommendations

• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• 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
• Wheel-free planar graphs

zbMATH Keywords

algorithmwheelinduced disjoint pathsthetainduced linkagetruemper configuration

Mathematics Subject Classification ID

Graph theory (including graph drawing) in computer science (68R10) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Structural characterization of families of graphs (05C75)

Cites Work

• Title not available (Why is that?)
• Decomposition by clique separators
• Graph minors. XIII: The disjoint paths problem
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• On the Computational Complexity of Combinatorial Problems
• The complexity of induced minors and related problems
• Detecting fixed patterns in chordal graphs in polynomial time
• Detecting 2-joins faster
• A linear time algorithm for the induced disjoint paths problem in planar graphs
• An Optimal Algorithm to Detect a Line Graph and Output Its Root Graph
• The three-in-a-tree problem
• Combinatorial optimization with 2-joins
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The four-in-a-tree problem in triangle-free graphs
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Clique or hole in claw-free graphs
• The \(k\)-in-a-path problem for claw-free graphs
• Induced disjoint paths in circular-arc graphs in linear time
• Induced disjoint paths in claw-free graphs
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring

Cited In (13)

• Few induced disjoint paths for \(H\)-free graphs
• Few induced disjoint paths for \(H\)-free graphs
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Graphs with no induced wheel and no induced antiwheel
• (Theta, triangle)‐free and (even hole, K4)‐free graphs—Part 1: Layered wheels
• Graphs with no even holes and no sector wheels are the union of two chordal graphs
• (Theta, triangle)‐free and (even hole, K4)‐free graphs. Part 2: Bounds on treewidth
• Detecting a Theta or a Prism
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs

This page was built for publication: The (theta, wheel)-free graphs. IV: Induced paths and cycles

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