Inapproximability results and bounds for the Helly and Radon numbers of a graph

DOI10.1016/J.DAM.2017.07.032MaRDI QIDQ2410232zbMATH OpenOpenAlexFDO

Authors Mitre C. Dourado, Aline R. da Silva

Publication date 17 October 2017

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

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

zbMATH Keywords

inapproximabilityupper boundbipartite graphsgeodetic convexityRadon numberHelly number

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Approximation algorithms (68W25) Planar graphs; geometric and topological aspects of graph theory (05C10) Helly-type theorems and geometric transversal theory (52A35)

Recommendations

• Inapproximability results for graph convexity parameters
• Inapproximability results for graph convexity parameters
• A Radon theorem for Helly graphs
• A Helly theorem for convexity in graphs
• On the geodetic rank of a graph

Cites work

• scientific article; zbMATH DE number 439012 (Why is no real title available?)
• scientific article; zbMATH DE number 1330032 (Why is no real title available?)
• scientific article; zbMATH DE number 480237 (Why is no real title available?)
• scientific article; zbMATH DE number 3068278 (Why is no real title available?)
• A Generalization of Radon's Theorem
• A Helly theorem for convexity in graphs
• Algorithmic and structural aspects of the P₃-Radon number
• An upper bound on the \(P_3\)-Radon number
• Complexity results related to monophonic convexity
• Convex sets in graphs. II: Minimal path convexity
• Convexity in Graphs and Hypergraphs
• Geodesic Convexity in Graphs
• Linear degree extractors and the inapproximability of max clique and chromatic number
• Open packing, total domination, and the P₃-Radon number
• Some remarks on simple tournaments

Cited in

(4)

• A Radon theorem for Helly graphs
• Inapproximability results for graph convexity parameters
• Inapproximability results for graph convexity parameters
• scientific article; zbMATH DE number 4142072 (Why is no real title available?)

This page was built for publication: Inapproximability results and bounds for the Helly and Radon numbers of a graph

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