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

bipartite graphsgeodetic convexityHelly numberinapproximabilityRadon numberupper bound

Mathematics Subject Classification ID

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

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

• 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
• 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?)
• 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

(6)

• A Radon theorem for Helly graphs
• Inapproximability results for graph convexity parameters
• scientific article; zbMATH DE number 4142072 (Why is no real title available?)
• Inapproximability results for graph convexity parameters
• The iteration time and the general position number in graph convexities
• On the hull and interval numbers of oriented graphs

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)