OBSTRUCTIONS TO TOTAL RAINBOW FORESTS IN EDGE-COLORED GRAPHS
MARWA MOSALLAM AND THOMAS ZASLAVSKY · 2026
Read OBSTRUCTIONS TO TOTAL RAINBOW FORESTS IN EDGE-COLORED GRAPHS by MARWA MOSALLAM AND THOMAS ZASLAVSKY (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-2606-31240.txt.
Introduction
Mosallam and Zaslavsky study total rainbow forests in edge-colored graphs. A rainbow forest uses edges that all carry different colors, and a total one uses every color exactly once. The pair ask when such a forest exists and, just as much, what blocks it from existing.
Using a necessary and sufficient condition for a total rainbow forest to exist, they show there are huge numbers of minimal obstruction graphs. A minimal obstruction fails the condition yet loses that status if changed at all, so it marks the exact edge of possibility. Their question grew from work on systems of curves on surfaces, where a rainbow criterion could help bound the largest such system, and it rests on the matroid intersection theorem.
Catalog record
| CREATOR | MARWA MOSALLAM AND THOMAS ZASLAVSKY |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 46 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2606.31240
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
OBSTRUCTIONS TO TOTAL RAINBOW FORESTS IN EDGE-COLORED GRAPHS MARWA MOSALLAM AND THOMAS ZASLAVSKY Abstract A total rainbow forest in an edge-colored graph is a forest that contains every edge color exactly once. Using a necessary and sufficient condition that a total rainbow forest exists, we demonstrate the existence of huge numbers of edge-colored graphs that are minimal obstructions to such existence. Keywords: edge-colored graph; rainbow spanning tree; total rainbow forest 2020 Mathematics Subject Classification: 05C15. 1 Introduction In an edge-colored graph, what is the maximum size of a rainbow (or “heterochromatic”) forest; that is, a forest whose edges all have different colors? Especially, does the graph have a total rainbow forest, whose edges represent every color? We study these questions and especially the obstructions to the existence of total rainbow forest. Our attention was drawn to this question by Tarik Aougab, who proposed to the first author that a criterion for the existence of a total rainbow tree, or forest, or connected subgraph, might help with the problem of a largest 1-system of curves on a genus g surface, and also told us about the use of the Matroid Intersection Theorem (which was suggested to him by Tony Huynh; see also [ 8 ] ). For a statement of the 1-system problem we refer the reader to, e.g., [ 2 , 11 ] . There has been considerable interest for years in rainbow forests, often on the existence of many edge-disjoint spanning rainbow forests in complete graphs; see for example [ 4 , 10 , 5 ] . Our focus is the existence and size of a single rainbow tree or forest, as for instance in [ 14 , 1 ] . Let G=(V,E) be a connected, edge-colored graph (not necessarily properly colored). Suzuki [ 14 , Theorem 7] proved an important theorem, which we restate here in terms of matroids (although Suzuki stated and proved it purely in terms of graphs): If G has order n and any number t of colors, then G has a rainbow spanning tree if and only if for every edge set A that is a union of color classes, n-1-r_{2}(E\setminus A)\leq r_{1}(A), where r_{1} and r_{2} are the rank functions of matroids M_{1} and M_{2} , both having the ground set E, such that in M_{1} a set is independent if it contains at most one edge of each color (this is known as the partition or transversal matroid; r_{1}(B) is the number of color classes in B ) and in M_{2} a set is independent if it does not contain a cycle (this is the cycle matroid). (See [ 13 ] for matroids.) We provide a complete proof of Suzuki’s theorem generalized to disconnected graphs, using the Matroid Intersection Theorem; see Theorem 3 . As far as we know, the use of these matroids and that theorem was introduced by Broersma and Li [ 3 , Section 2] ; they observed that a rainbow forest is an edge set that is independent in both the cycle matroid and the partition matroid and they used this fact to determine the largest size of a rainbow forest [ 3 , Lemma 3] . (We learned of the Matroid Intersection approach from Tony Huynh, via Tarik Aougab.) In our study, usually t=n-1 (for connected G ) so Suzuki’s condition simplifies to r_{2}(B)\geq r_{1}(B) for every set B that is a union of color classes (Theorem 5 ), which is our necessary and sufficient condition for existence of a total rainbow forest in terms of matroid ranks. This simpler condition suggests a new approach to the existence problem by way of forbidden subgraphs, which we call obstructions to the existence of a rainbow spanning tree (Section 4 ). An obstruction is simply an edge-colored graph that has too many colors to contain a total rainbow forest. We show that there are many and diverse obstructions of any order n (barring trivially small n ) that are minimal, in the sense of not having a smaller obstruction. That is our principal contribution. 2 The Rainbow Forest Inequality We assume throughout that G=(V,E) is a simple graph of order n , edge colored with total number of colors t . The number of connected components of a graph, written c(\ ) , is part of the cycle-matroid rank formula r_{2}(B)=n-c(V,B) for an edge set B\subseteq E . We will use the concept of isomorphism of edge-colored graphs. For us, isomorphic edge-colored graphs are not essentially different. Definition 1 . Let G_{1} and G_{2} be edge-colored graphs with respective color sets C_{1} and C_{2} and edge-color functions c_{1}:E_{1}\to C_{1} and c_{2}:E_{2}\to C_{2} . An isomorphism of G_{1} and G_{2} , written G_{1}\cong G_{2} , is a pair \theta,f consisting of a graph isomorphism \theta:G_{1}\to G_{2} and a color-set bijection f:C_{1}\to C_{2} such that c_{2}(\theta(e))=f(c_{1}(e)) for each edge e\in E_{1} . In other words, an isomorphism of edge-colored graphs G and G^{\prime} is a graph isomorphism that preserves the partition of the edge set into color classes; it need not preserve the colors themselves. Now we define the fundamental concept of our work. Definition 2 . A rainbow or heterochromatic subgraph of an edge-colored graph G is a subgraph such that no color appears more than once amongst the edges of the subgraph. We are especially interested in spanning trees or forests. If our forest need not contain the total number of colors t but need only contain some of them, call u the number of colors desired in the forest, where u\leq t. This will be a total rainbow forest if u=t . Definition 3 . The Rainbow Forest Inequality is defined as follows: \forall A\subseteq E(G){:}\ r_{1}(A)+r_{2}(E\setminus A)\geq t. Given a number of colors u\leq t , the Rainbow Forest Inequality for u is defined as follows: \forall A\subseteq E(G){:}\ r_{1}(A)+r_{2}(E\setminus A)\geq u. Proposition 1 . If G satisfies the Rainbow Forest Inequality, the total number of colors t has to satisfy t\leq n-c(G). Proof. Set A=\emptyset in the Rainbow Forest Inequality. ∎ Definition 4 . The Partial Rainbow Inequality of an edge set A is defined as follows: r_{1}(A)+r_{2}(E\setminus A)\geq t. Given a number of colors u\leq t , the Partial Rainbow Inequality for u of A is defined as follows: r_{1}(A)+r_{2}(E\setminus A)\geq u. To prove Theorem 3 below we need the previously defined matroids M_{1} and M_{2} on the edge set of G . The connection is given by interpreting the Matroid Intersection Theorem. We think of a matroid as a pair (E,\mathcal{I}) where E is the ground set and \mathcal{I} is the class of independent sets. Theorem 2 (Edmonds’ Matroid Intersection Theorem [ 13 , Theorem 11.3.15] , [ 6 , Ch. 3, Exercise 40(c)] ) . For any two matroids M_{1}=(E,\mathcal{I}_{1}) and M_{2}=(E,\mathcal{I}_{2}) we have \max_{I\in{\mathcal{I}}_{1}\cap{\mathcal{I}}_{2}}|I|=\min_{A\subseteq E}[r_{1}(A)+r_{2}(E\setminus A)] where r_{1} and r_{2} are the respective rank functions of M_{1} and M_{2} . This gives our first theorem. (A partial approach to this theorem is found in [ 3 , discussion after Lemma 3] .) Theorem 3 . Consider an edge-colored graph. Let t be the total number of colors on the edges. For a total rainbow forest to exist, it is necessary and sufficient