On neighborhood-Helly graphs

DOI10.1016/J.DAM.2016.04.029zbMATH Open1350.05167OpenAlexW2475227852MaRDI QIDQ344856FDOQ344856

Authors: Marina Groshaus, Min Chih Lin, Jayme L. Szwarcfiter 

Publication date: 24 November 2016

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

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

Recommendations

• Helly type theorem and graphs
• scientific article; zbMATH DE number 2096437
• On hereditary Helly classes of graphs
• Publication:4940014
• Faster recognition of clique-Helly and hereditary clique-Helly graphs

zbMATH Keywords

complexityextensionsHelly propertyNP-hardness

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Graph theory (05C99) Helly-type theorems and geometric transversal theory (52A35)

Cites Work

• Topics in Intersection Graph Theory
• Graph Classes: A Survey
• Algorithms on circular-arc graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Linear-time recognition of Helly circular-arc models and graphs
• The edge intersection graphs of paths in a tree
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Dually Chordal Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Clique graphs and Helly graphs
• Complexity aspects of the Helly property: graphs and hypergraphs
• Biclique graphs and biclique matrices
• Title not available (Why is that?)
• On hereditary Helly classes of graphs
• Diamond-free circle graphs are Helly circle
• Improved algorithms for recognizing \(p\)-Helly and hereditary \(p\)-Helly hypergraphs
• Dismantling absolute retracts of reflexive graphs
• Efficient characterizations of \(n\)-chromatic absolute retracts
• Hypergraphes arbores
• \(r\)-dominating cliques in graphs with hypertree structure
• Domination in quadrangle-free Helly graphs
• A polynomial algorithm for the strong Helly property
• Normal Helly circular-arc graphs and its subclasses
• Faster recognition of clique-Helly and hereditary clique-Helly graphs
• Biclique-Helly graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Absolute reflexive retracts and absolute bipartite retracts

Cited In (10)

• Nearest-neighbor graphs on the cantor set
• Title not available (Why is that?)
• Helly type theorem and graphs
• Helly-gap of a graph and vertex eccentricities
• A note on small directed graphs as neighborhood graphs
• Title not available (Why is that?)
• Further results on the neighbourhood number of a graph
• On hereditary Helly classes of graphs
• Degeneracy graphs and the neighbourhood problem
• Title not available (Why is that?)

This page was built for publication: On neighborhood-Helly graphs

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