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

DOI10.1016/J.JCTB.2020.06.002MaRDI QIDQ2221936zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cites work

• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• 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
• Clique or hole in claw-free graphs
• Combinatorial optimization with 2-joins
• Corrigendum to: On the complexity of testing for odd holes and induced odd paths
• Decomposition by clique separators
• Detecting 2-joins faster
• Detecting fixed patterns in chordal graphs in polynomial time
• Graph minors. XIII: The disjoint paths problem
• Induced disjoint paths in circular-arc graphs in linear time
• Induced disjoint paths in claw-free graphs
• On the Computational Complexity of Combinatorial Problems
• 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
• The \(k\)-in-a-path problem for claw-free graphs
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• The complexity of induced minors and related problems
• The four-in-a-tree problem in triangle-free graphs
• The three-in-a-tree problem

Cited in

(15)

• 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
• The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
• The (theta, wheel)-free graphs. II: Structure theorem
• The (theta, wheel)-free graphs. III: Cliques, stable sets and coloring
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Induced disjoint paths and connected subgraphs for H-free graphs
• Induced disjoint paths and connected subgraphs for \(H\)-free graphs
• Improved algorithms for perfect graphs and odd holes

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)