Rainbow Separating Path Systems
Alexander Clifton, George Kontogeorgiou, S Taruni, Ana Trujillo-Negrete · 2026
Read Rainbow Separating Path Systems by Alexander Clifton, George Kontogeorgiou, S Taruni, Ana Trujillo-Negrete (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2604-16046.txt.
Introduction
Clifton and three colleagues introduce a colorful version of separating path systems, in which two edges can only be separated by two paths of distinct colors. They calculate the minimum sizes of such systems for various standard graph classes and numbers of colors. With respect to this setup, they identify three possible asymptotic behaviors for a graph class as colors go to infinity, and find a wide range of examples displaying each behavior.
Catalog record
| CREATOR | Alexander Clifton, George Kontogeorgiou, S Taruni, Ana Trujillo-Negrete |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 110611 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2604.16046
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Rainbow Separating Path Systems Alexander Clifton, George Kontogeorgiou, S Taruni, Ana Trujillo-Negrete Abstract We introduce a colorful version of separating path systems, in which two edges can only be separated from each other by two paths of distinct colors. We calculate the minimum sizes of such systems for various standard classes of graphs and numbers of colors. With respect to this setup, we identify three possible asymptotic behaviors for a class of graphs as the number of colors goes to infinity, and we find a wide range of examples that display each of these behaviors. 1 Introduction Let G be a graph and let \mathscr{P} be a set of paths of G . We say that \mathscr{P} is a strongly separating path system if for every ordered pair of distinct edges (e,f)\in E(G)^{2} , there exists a path in \mathscr{P} that contains e and avoids f . We say that \mathscr{P} is a weakly separating path system if for every pair of edges \{e,f\}\in{E(G)\choose 2} there exists a path in \mathscr{P} that contains exactly one of them. The strong (resp. weak ) separation number of G , denoted ssp(G) (resp. wsp(G) ), is the least possible size of a path system that strongly (resp. weakly) separates E(G) . Since strongly separating path systems are also weakly separating, wsp(G)\leq ssp(G) for every graph G . The problem of computing the separation numbers of various graphs is now over a decade old. It was first stated in its current form by Gyula O. H. Katona (see [ 6 ] ). Falgas-Ravry, Kittipassorn, Korándi, Letzter and Narayanan [ 6 ] were the first to publish results in the weak setting, whereas Balogh, Csaba, Martin and Pluhár [ 2 ] pioneered the strong setting. Both groups conjectured a linear upper bound in the number of vertices; an elegant proof of this conjecture was later given by Bonamy, Botler, Dross, Naia and Skokan [ 4 ] , establishing the bound ssp(G)\leq 19|V(G)| . Moreover, these numbers have been calculated exactly for trees [ 2 , 1 ] , asymptotically for dense, almost-regular, robustly connected graphs [ 7 ] , and up to an additive constant for complete graphs [ 8 ] . Some authors have recently studied variations of this topic, such as path systems that separate vertices instead of edges [ 3 , 9 ] and separation systems that consist of subdivisions of a given graph instead of paths [ 5 ] . In this paper we introduce a generalization of separating path systems, namely rainbow separating path systems . Definition 1.1 . A multiset of paths \mathscr{P} in a graph G is a k -rainbow separating path system (or k -RSPS for short) if its elements can be colored with k\in\{2,3,\dots\} colors so that for every pair of edges \{e_{1},e_{2}\}\in{E(G)\choose 2} there exist paths P_{1},P_{2}\in\mathscr{P} of distinct colors such that e_{1}\in P_{1}\not\owns e_{2} and e_{2}\in P_{2}\not\owns e_{1} . The k -rainbow separation number of G , denoted by c_{k}(G) , is the smallest cardinality of a k -RSPS of G . Clearly, c_{k}(G) is non-increasing in k . The first thing to notice is that strongly separating path systems are in fact RSPS’s in which we are allowed the use of infinitely many colors, so we can write ssp(G)=c_{\infty}(G) . RSPS’s are therefore the result of a natural restriction imposed on strongly separating path systems; we ask, quite simply, what if we only had some specified finite number of available colors? One might expect that this would always force us to use significantly more paths in order to separate E(G) . Let us explain exactly how we quantify this. For a graph G and a number k\in\{2,3,\dots\}\cup\{\infty\} , we define the k - rainbow separation ratio r_{k}(G):=\frac{c_{k}(G)}{c_{\infty}(G)}. As we shall see (Proposition 1.5 ), r_{k}(G)\leq 2 for every graph G and k\in\{2,3,\dots\}\cup\{\infty\} . Given a class (that is, an infinite family) \Sigma of graphs, the k -rainbow separation ratio of \Sigma is defined to be r_{k}(\Sigma):=\limsup_{G\in\Sigma}r_{k}(G). The k -rainbow separation ratio measures the penalty that we incur for attempting to separate the edges of graphs of \Sigma with only k (rather than infinitely many) colors. Surprisingly, we will see that, in many cases, a small number of colors k suffices to (almost) attain the strong separation number, that is, to achieve r_{k}(\Sigma)=1 . For example, for any tree T on n vertices, four colors suffice to rainbow separate E(T) with at most n-1 paths (Theorem 3.7 ), which is tight for pathy classes of trees (i.e. trees with o(n) vertices of degree at least 3 ) up to a sublinear error. In particular, for the class \mathcal{SP} of spiders we have r_{4}(\mathcal{SP})=1 . However, three colors are not enough: we show that there exist spiders on n vertices that cannot be 3 -rainbow separated with fewer than \frac{17}{16}(n-1)-3 paths (Theorem 3.5 ). In contrast, the strong separation number of a spider on n vertices is n-1 , so r_{3}(\mathcal{SP})\geq\frac{17}{16} . For two colors, the difference is even more pronounced, as stars require 2\lfloor\frac{2(n-1)}{3}\rfloor paths for 2 -rainbow separation (Theorem 2.3 ), so r_{2}(\mathcal{SP})\geq\frac{4}{3} . On the other extreme, we show that there exist classes \Sigma of graphs for which, no matter how large the (finite and fixed) number k of colors that we are allowed, we need many more paths to rainbow separate the edges of graphs from \Sigma than to strongly separate them. That is, there exists some c>1 for which we have a uniform bound r_{k}(\Sigma)>c for all k\in\{2,3,\dots\} . Examples of such classes include the class \mathcal{K} of complete graphs (Theorem 4.1 ), for which c_{k}(K_{n})\geq\frac{3}{2}(n-O_{k}(1))>n+9\geq c_{\infty}(K_{n}), so that r_{k}(\mathcal{K})\geq\frac{3}{2} for all k\in\{2,3,\dots\} , or in general the class \mathcal{G}_{p} of Erdős-Rényi random graphs with constant probability p (Theorem 4.2 ), for which c_{k}(G(n,p))\geq\frac{3}{2}p(n-O_{k}(1))>\left(\sqrt{3p+1}-1+o(1)\right)n=c_{\infty}(G(n,p)), so that r_{k}(\mathcal{G}_{p})\geq\frac{3p}{2(\sqrt{3p+1}-1)}>1 . Finally, there are classes \Sigma of graphs that fall in-between; the sequence r_{k}(\Sigma) converges to 1 as k\rightarrow\infty , without ever attaining equality. An example of such a class is the class \mathcal{BT} of complete binary trees (Theorem 4.5 ). Let us define precisely these distinct asymptotic behaviors. We say that a class \Sigma of graphs is rainbow separable if for every \varepsilon>0 , there exists k\in\mathbb{N} such that r_{k}(\Sigma)<1+\varepsilon . If a class \Sigma of graphs is rainbow separable, then we define its chromatic separation number to be \chi_{rs}(\Sigma):=\min\{k\in\{2,3,\dots\}\cup\{\infty\}|r_{k}(\Sigma)=1\}. For example, the class \mathcal{K} of complete graphs is not rainbow separable. The class \mathcal{SP} of spiders has \chi_{rs}(\mathcal{SP})=4 , whereas the class \mathcal{BT} of complete binary trees has \chi_{rs}(\mathcal{BT})=\infty . This raises some intriguing questions. What determines whether a class \Sigma of graphs is rainbow separable? If it is, what determines its chromatic separation number? Can any k\in\{2,3,\dots\} be the chromatic separation number of some class? Some questions about the asymptotic behavior of rainbow separation ratios are handled in Section 4 . Before that, in Section 2 and Section 3 , we display results concerning the k -rainbow separation numbers of various standard classes of graphs for k=2 , 3 and 4 . Specifically, we exactly determine or tightly bound these numbers for paths, cycles, stars, spiders, and pathy trees. In this manner, we obtain many working examples, establish useful tools,