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

DOI10.1016/j.dam.2013.04.026zbMath1285.05155OpenAlexW2129430342MaRDI QIDQ2444540

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 algorithms (graph-theoretic aspects) (05C85) Graph operations (line graphs, products, etc.) (05C76)

Related Items (3)

Solving the Weighted Stable Set Problem in Claw-Free Graphs via Decomposition ⋮ Unnamed Item ⋮ A faster algorithm to recognize even-hole-free graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Finding and counting small induced subgraphs efficiently
• The strong perfect graph theorem
• The monotone circuit complexity of Boolean functions
• Bull-free Berge graphs are perfect
• Recognizing claw-free perfect graphs
• A strengthening of Ben Rebea's lemma
• A \(max \{m, n \}\) algorithm for determining the graph H from its line graph G
• Recognizing Berge graphs
• Coloring quasi-line graphs
• Linear-Time Representation Algorithms for Proper Circular-Arc Graphs and Proper Interval Graphs
• Fibonacci heaps and their uses in improved network optimization algorithms
• Smallest Odd Holes in Claw-Free Graphs (Extended Abstract)

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