Azarbaijan Shahid Madani University Communications in Combinatorics and Optimization 2538-2128 Articles in Press 2025 03 13 On maximum tolerant Radon partitions for all-paths convexity in graphs 14918 10.22049/cco.2025.29418.1986 EN Sreekumar Sreedharan Department of Mathematics, Government College for Women, Thiruvananthapuram-695014, India Manoj Changat Department of Futures Studies, University of Kerala, Thiruvananthapuram-695581, India Kannan Balakrishnan Department of Computer Applications, Cochin University of Science and Technology, Kochi-682022, India Journal Article 2024 01 31 In a connected graph $G$, the all-paths transit function $A(u,v)$, consists of the set of all vertices in the graph $G$ which lies on some path connecting $u$ and $v$.  Convexity obtained by the all-paths transit function is called all-paths convexity.  A Radon partition of a set $P$ of vertices of a graph $G$ is a partition of $P$ into two disjoint non-empty subsets such that their convex hulls intersect.  A Radon partition $(P_t, Q_t)$ of $P$ is called $t$-tolerant Radon partition, if for any set $S\subseteq P$ with $|S|\le t$,  the intersection of the convex hulls  $\langle P_t\setminus S \rangle \cap \langle Q_t\setminus S \rangle \neq \emptyset$.  This paper is devoted to $t$-tolerant Radon partitions for the all-paths convexity of connected simple undirected graphs.  It is proved that the minimum number of vertices needed for $t$-tolerant Radon partition is $2t+4$. But, some selection of $2t+4$ vertices of $G$ has a $(t+1)$-tolerant Radon partition.  In this paper, we discuss the necessary and sufficient condition to the existence of $(t+1)$-tolerant Radon partition for $2t+4$ vertices of $G$.  We also develop algorithms to construct the Radon partition, $t$-tolerant Radon partition, and $(t+1)$-tolerant Radon partition of a set of $2t+4$ vertices, if it exists. https://comb-opt.azaruniv.ac.ir/article_14918_0f477fb7399bd4acc129ea7d264039d0.pdf