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

DOI10.1016/J.DAM.2013.04.026MaRDI QIDQ2444540zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

claw-free graphodd hole

Mathematics Subject Classification ID

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

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

Cites work

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

Cited in

(6)

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

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)