Algorithmic and structural aspects of the \(P_3\)-Radon number

DOI10.1007/s10479-013-1320-9zbMath1270.05062OpenAlexW2044122222MaRDI QIDQ363552

Mitre C. Dourado, Dieter Rautenbach, Alexandre Toman, Vinícius Fernandes dos Santos, Jayme Luiz Szwarcfiter, Philipp Matthias Schäfer

Publication date: 3 September 2013

Published in: Annals of Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10479-013-1320-9

zbMATH Keywords

graph convexityRadon numberRadon partition

Mathematics Subject Classification ID

Paths and cycles (05C38) Planar graphs; geometric and topological aspects of graph theory (05C10) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

On the \(\Delta \)-interval and the \(\Delta \)-convexity numbers of graphs and graph products, Inapproximability results and bounds for the Helly and Radon numbers of a graph, Characterization and recognition of Radon-independent sets in split graphs, The convexity of induced paths of order three and applications: complexity aspects, An upper bound on the \(P_3\)-Radon number

Cites Work

• Unnamed Item
• Unnamed Item
• Irreversible conversion of graphs
• \(k\)-domination and \(k\)-independence in graphs: A survey
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Convex sets in graphs. II: Minimal path convexity
• On two-path convexity in multipartite tournaments
• Embedding tournaments in simple tournaments
• Some remarks on simple tournaments
• Convexity in Graphs and Hypergraphs
• On the Carathéodory Number for the Convexity of Paths of Order Three
• The complexity of theorem-proving procedures