Faster recognition of clique-Helly and hereditary clique-Helly graphs

DOI10.1016/j.ipl.2007.02.017zbMath1183.05059OpenAlexW2025463213MaRDI QIDQ2379939

Min Chih Lin, Jayme Luiz Szwarcfiter

Publication date: 24 March 2010

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2007.02.017

zbMATH Keywords

algorithmsHelly propertyclique-Helly graphshereditary clique-Helly graphsdisk-Helly graphshereditary disk-Helly graphs

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Related Items (12)

Fast deterministic algorithms for computing all eccentricities in (hyperbolic) Helly graphs ⋮ On neighborhood-Helly graphs ⋮ Helly-gap of a graph and vertex eccentricities ⋮ Beyond Helly graphs: the diameter problem on absolute retracts ⋮ A story of diameter, radius, and (almost) Helly property ⋮ Distance problems within Helly graphs and \(k\)-Helly graphs ⋮ On the generalized Helly property of hypergraphs, cliques, and bicliques ⋮ On edge-sets of bicliques in graphs ⋮ Improved algorithms for recognizing \(p\)-Helly and hereditary \(p\)-Helly hypergraphs ⋮ The chromatic gap and its extremes ⋮ On minimal forbidden subgraph characterizations of balanced graphs ⋮ On the clique behavior and Hellyness of the complements of regular graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Clique graphs and Helly graphs
• Dismantling absolute retracts of reflexive graphs
• A hierarchy of self-clique graphs
• Vertex-to-vertex pursuit in a graph
• A polynomial algorithm for the strong Helly property
• A characterization of clique graphs
• Über iterierte Clique-Graphen
• Graph Classes: A Survey
• Self‐clique graphs and matrix permutations
• A partial characterization of clique graphs

This page was built for publication: Faster recognition of clique-Helly and hereditary clique-Helly graphs