A new characterization of HH-free graphs

DOI10.1016/j.disc.2007.08.063zbMath1226.05238OpenAlexW2010126997MaRDI QIDQ942119

R. Sritharan, Jeremy P. Spinrad, Dieter Kratsch

Publication date: 4 September 2008

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

Full work available at URL: https://doi.org/10.1016/j.disc.2007.08.063

zbMATH Keywords

algorithmgraphhousehole2-pairMeyniel

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Graph theory (including graph drawing) in computer science (68R10) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items

Symmetric graph-theoretic roles of two-pairs and chords of cycles ⋮ Resolving prime modules: the structure of pseudo-cographs and galled-tree explainable graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Meyniel weakly triangulated graphs. I: Co-perfect orderability
• Matrix multiplication via arithmetic progressions
• A new property of critical imperfect graphs and some consequences
• A fast algorithm for coloring Meyniel graphs
• Almost diameter of a house-hole-free graph in linear time via LexBFS
• An efficient algorithm for finding a two-pair, and its applications
• Optimizing weakly triangulated graphs
• A characterization of some graph classes with no long holes
• Recognizing Berge graphs
• An \(O(n^2)\) algorithm to color Meyniel graphs
• Finding houses and holes in graphs