Finding a smallest odd hole in a claw-free graph using global structure

DOI10.1016/J.DAM.2013.04.026zbMATH Open1285.05155OpenAlexW2129430342MaRDI QIDQ2444540FDOQ2444540

Authors: W. Sean Kennedy, Andrew D. King 

Publication date: 10 April 2014

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2013.04.026

Recommendations

• Smallest odd holes in claw-free graphs (extended abstract)
• Odd Hole Recognition in Graphs of Bounded Clique Size
• Clique or hole in claw-free graphs
• Claw-free graphs. V. Global structure
• scientific article; zbMATH DE number 6302876
• The structure of claw-free graphs
• Complexity of clique-coloring odd-hole-free graphs
• Exact algorithms for finding longest cycles in claw-free graphs
• Structure and algorithms for (cap, even hole)-free graphs
• The \(k\)-in-a-path problem for claw-free graphs

zbMATH Keywords

claw-free graphodd hole

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75) Graph operations (line graphs, products, etc.) (05C76)

Cites Work

• Fibonacci heaps and their uses in improved network optimization algorithms
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• The strong perfect graph theorem
• Recognizing Berge graphs
• The structure of claw-free graphs
• The monotone circuit complexity of Boolean functions
• Finding and counting small induced subgraphs efficiently
• Bull-free Berge graphs are perfect
• Coloring quasi-line graphs
• A strengthening of Ben Rebea's lemma
• Recognizing claw-free perfect graphs
• Title not available (Why is that?)
• Smallest odd holes in claw-free graphs (extended abstract)

Cited In (5)

• Smallest odd holes in claw-free graphs (extended abstract)
• A faster algorithm to recognize even-hole-free graphs
• Odd Hole Recognition in Graphs of Bounded Clique Size
• A faster algorithm to recognize even-hole-free graphs
• Solving the weighted stable set problem in claw-free graphs via decomposition

This page was built for publication: Finding a smallest odd hole in a claw-free graph using global structure

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