On the Anti-Ramsey Number of Spanning Linear Forests with Paths of Lengths 2 and 3

Ali Ghalavand, Xueliang Li · 2025

Read On the Anti-Ramsey Number of Spanning Linear Forests with Paths of Lengths 2 and 3 by Ali Ghalavand, Xueliang Li (2025) 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-2509-25949.txt.

Introduction

Ali Ghalavand and Xueliang Li solve an anti-Ramsey number problem in this 2025 mathematics paper. Color the edges of a complete graph, using as many colors as possible while avoiding a rainbow copy of a target shape, where every edge has a distinct color. The target here is a spanning linear forest: disjoint three-vertex paths plus a matching. A recent paper settled part of the range.

The authors settle the full spanning case, where the forest uses every vertex, for all remaining parameter values with no extra restrictions. Their count gives the exact maximum number of colors. The result completes the picture begun by the earlier work on this forest family. Such exact values are prized in Ramsey theory, where most problems resist closure.

Catalog record

CREATORAli Ghalavand, Xueliang Li
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE53 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-25949

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

On the Anti-Ramsey Number of Spanning Linear Forests with Paths of Lengths 2 and 3 Ali Ghalavand, Xueliang Li Abstract An edge-coloring of a graph G G assigns a color to each edge in the edge set E ⁡ ( G ) E(G) . A graph G G is considered to be rainbow under an edge-coloring if all of its edges have different colors. For a positive integer n n , the anti-Ramsey number of a graph G G , denoted as A ​ R ​ ( n , G ) AR(n,G) , represents the maximum number of colors that can be used in an edge-coloring of the complete graph K n K_{n} without containing a rainbow copy of G G . This concept was introduced by Erdős et al. in 1975. The anti-Ramsey number for the linear forest k ​ P 3 ∪ t ​ P 2 kP_{3}\cup tP_{2} has been extensively studied for two positive integers k k and t t . Formulations exist for specific values of t t and k k , particularly when k ≥ 2 k\geq 2 , t ≥ k 2 − k + 4 2 t\geq\frac{k^{2}-k+4}{2} , and n ≥ 3 ​ k + 2 ​ t + 1 n\geq 3k+2t+1 . In this work, we present the anti-Ramsey number of the linear forest k ​ P 3 ∪ t ​ P 2 kP_{3}\cup tP_{2} for the case where k ≥ 1 k\geq 1 , t ≥ 2 t\geq 2 , and n = 3 ​ k + 2 ​ t n=3k+2t . Notably, our proof for this case does not require any specific relationship between k k and t t . a Center for Combinatorics and LPMC, Nankai University, Tianjin 300071, China Keywords: rainbow graph; anti-Ramsey number; spanning linear forest. 1 Introduction In this study, we examine the anti-Ramsey number of forests composed solely of paths of lengths two and three. We will begin by defining key concepts and discussing their historical context. Let G be a finite and simple graph with a vertex set V(G) and an edge set E(G) . An edge-coloring of a graph G is a mapping c that assigns a color to each edge in E(G) . The graph G is considered to be rainbow under the edge coloring c if all of its edges have different colors. For an edge e in G , the notation c(e) indicates the color assigned to the edge e by the map c . For a subset E^{\prime} of E(G) , the notation c(E^{\prime}) represents the set of colors assigned to the edges in E^{\prime} , that is, c(E^{\prime})=\{c(e):e\in E^{\prime}\} . Similarly, for a subgraph H of G , the notation c(H) represents the set of colors assigned to the edges in H , specifically, c(H)=\{c(e):e\in E(H)\} . Let V^{\prime} be a subset of the vertex set V(G) of a graph G . The subgraph of G that is induced by V^{\prime} is denoted by G[V^{\prime}] . This subgraph has the vertex set V^{\prime} , and two vertices in it are considered adjacent if and only if they are adjacent in the original graph G . For another graph G^{\prime} , the disjoint union of G and G^{\prime} , denoted as G\cup G^{\prime} , is a new graph that includes both G and G^{\prime} . The vertex set of this new graph is given by V(G\cup G^{\prime})=V(G)\cup V(G^{\prime}) , while the edge set is defined as E(G\cup G^{\prime})=E(G)\cup E(G^{\prime}) . Additionally, for any positive integer a , the notation aG refers to the disjoint union of a copies of the graph G . Let t be a positive integer. We will use the notation [t] to represent the set of natural numbers \{1,2,\ldots,t\} . For clarity, we define [0]=\emptyset . The notations K_{t} , C_{t} , and P_{t} refer to the complete graph, the cycle graph, and the path graph on t vertices, respectively. Let n be a positive integer. The anti-Ramsey number of a graph G , denoted as AR(n,G) , represents the maximum number of colors in an edge-coloring of the complete graph K_{n} that does not contain a rainbow copy of G . This concept was first introduced by Erdős et al. in 1975 [ 3 ] , who established its connection to Turán numbers and conjectured the anti-Ramsey numbers for paths and cycles. Inspired by their work, a particularly active area of research has focused on characterizing anti-Ramsey numbers for graphs made up of multiple small, disjoint components. A key example of this is a matching, which consists of disjoint edges; the anti-Ramsey numbers for matchings in complete graphs are now fully understood, as referenced in [ 2 , 5 , 7 , 9 , 14 ] . In recent years, the focus has shifted from single matchings to more complex structures. Notably, researchers have begun exploring anti-Ramsey numbers for graphs formed by the vertex-disjoint union of small connected graphs and matchings. Simonovits and Sós [ 13 ] proved that if t\geq 2 and n is sufficiently large, then the following holds: AR(n,P_{t})={\left\lfloor\frac{t-1}{2}\right\rfloor\choose 2}+\left(\left\lfloor\frac{t-1}{2}\right\rfloor-1\right)\left(n-\left\lfloor\frac{t-1}{2}\right\rfloor+1\right)+1+\epsilon, where \epsilon=1 if t is even and \epsilon=0 otherwise. Montellano-Ballesteros and Neumann-Lara [ 11 ] proved that for any n\geq t\geq 3 , AR(n,C_{t})={t-1\choose 2}\left\lfloor\frac{n}{t-1}\right\rfloor+\left\lceil\frac{n}{t-1}\right\rceil+{n\mod(t-1)\choose 2}. Schiermeyer [ 12 ] showed that for all t\geq 2 and n\geq 3t+3 , the following holds: AR(n,tP_{2})={t-2\choose 2}+(t-2)(n-t+2)+1. Then, Chen et al. [ 2 ] and Fujita et al. [ 5 ] demonstrated that for all t\geq 2 and n\geq 2t+1 : AR(n,tP_{2})=\begin{cases}(t-2)(2t-3)+2&\text{when }n\leq\frac{5t-7}{2},\\ (t-2)(n-\frac{t-1}{2})+2&\text{when }n\geq\frac{5t-7}{2}.\end{cases} Finally, the remaining case n=2t was addressed by Haas and Young [ 7 ] , who confirmed the conjecture made in [ 5 ] . They showed that if n=2t , then: AR(n,tP_{2})=\begin{cases}\frac{1}{2}(t-2)(3t+1)+2&\text{when }3\leq t\leq 6,\\ (t-2)(2t-3)+3&\text{when }t\geq 7.\end{cases} Bialostocki et al. [ 1 ] examined the anti-Ramsey number of graphs with at most four edges and proved that AR(n,P_{3}\cup P_{2})=2 when n\geq 5 and AR(n,P_{3}\cup 2P_{2})=n when n\geq 7 . For more general graph classes, Gilboa and Roditty [ 6 ] provided upper bounds on the anti-Ramsey numbers of L\cup tP_{2} and L\cup tP_{3} under specific conditions. They proved that, for sufficiently large n , \bullet AR(n,P_{k+1}\cup tP_{3})=(t+\lfloor\frac{k}{2}\rfloor-1)(n-\frac{t+\lfloor\frac{k}{2}\rfloor}{2})+1+(k\mod 2) when k\geq 3 ; \bullet AR(n,kP_{3}\cup tP_{2})=(k+t-2)(n-\frac{t+k-1}{2})+1 when k,t\geq 2 ; \bullet AR(n,P_{2}\cup tP_{3})=(t-1)(n-\frac{t}{2})+2 when t\geq 1 ; \bullet AR(n,P_{3}\cup tP_{2})=(t-1)(n-\frac{t}{2})+1 when t\geq 2 ; \bullet AR(n,P_{4}\cup tP_{2})=t(n-\frac{t+1}{2})+1 when t\geq 1 ; \bullet AR(n,C_{3}\cup tP_{2})=t(n-\frac{t+1}{2})+1 when t\geq 1 ; \bullet AR(n,tP_{3})=(t-1)(n-\frac{t}{2})+1 when t\geq 1 . He and Jin [ 8 ] established that if t\geq 2 and n\geq 2t+3 , then AR(n,P_{3}\cup tP_{2})=\begin{cases}t(2t-1)+1&\text{when }2t+3\leq n\leq\left\lfloor\frac{5t+2}{2}+\frac{1}{t-1}\right\rfloor,\\ \frac{1}{2}(t-1)(2n-t)+1&\text{when }n\geq\left\lceil\frac{5t+2}{2}+\frac{1}{t-1}\right\rceil.\end{cases} They also proved that if t\geq 2 and n\geq 2t+7 , then AR(n,2P_{3}\cup tP_{2})=\begin{cases}(t+1)(2t+3)+1&\text{when }2t+7\leq n\leq\left\lfloor\frac{5t+11}{2}+\frac{3}{t}\right\rfloor,\\ \frac{1}{2}t(2n-t-1)+1&\text{when }n\geq\left\lceil\frac{5t+11}{2}+\frac{3}{t}\right\rceil.\end{cases} Fang et al. [ 4 ] considered F to be a linear forest with components of order p_{1},p_{2},\ldots,p_{t} , where t\geq 2 and p_{i}\geq 2 for 1\leq i\leq t , and at least one p_{i} is even. They proved that for sufficiently large n , AR(n,F)=\left(\sum_{i\in[t]}n\left\lfloor\frac{p_{i}}{2}\right\rfloor-\epsilon\right)n+{O}(1), where \epsilon=1 if all p_{i} are odd, and \epsilon=2 otherwise. Following this, Xie et al. [ 15 ] established an exact expression for the anti-Ramsey numbers of linear forests containing even components. They proved that if at

Read the complete text