An upper bound on the \(P_3\)-Radon number

DOI10.1016/j.disc.2012.05.002zbMath1245.05071MaRDI QIDQ442343

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

Publication date: 10 August 2012

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

Full work available at URL: https://doi.org/10.1016/j.disc.2012.05.002

zbMATH Keywords

graph convexity; Radon number; Radon partition

Mathematics Subject Classification ID

05C35: Extremal problems in graph theory

52A35: Helly-type theorems and geometric transversal theory

Related Items

Complexity aspects of the triangle path convexity, Radon numbers for trees, Characterization and recognition of Radon-independent sets in split graphs, On the \(P_3\)-hull number of Kneser graphs, A general framework for path convexities, Computing the hull number in toll convexity, Inapproximability results and bounds for the Helly and Radon numbers of a graph

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Algorithmic and structural aspects of the \(P_3\)-Radon number
• On finite convexity spaces induced by sets of paths in graphs
• 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
• A Radon theorem for Helly graphs
• Partition numbers for trees and ordered sets
• On triangle path convexity in graphs
• The partition conjecture
• On two-path convexity in multipartite tournaments
• Embedding tournaments in simple tournaments
• Some remarks on simple tournaments
• The All-Paths Transit Function of a Graph
• Convexity in Graphs and Hypergraphs
• A Generalization of Radon's Theorem