On Neutral Edge Sets in Anti-Ramsey Numbers
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918244402593792 |
|---|---|
| author | Ghalavand, Ali Jie, Qing Jin, Zemin Li, Xueliang Pan, Linshu |
| author_facet | Ghalavand, Ali Jie, Qing Jin, Zemin Li, Xueliang Pan, Linshu |
| contents | The anti-Ramsey number of a graph $G$, introduced by Erdős et al.\ in 1975, is the maximum number of colors in an edge-coloring of the complete graph $K_n$ that avoids a rainbow copy of $G$. We call a subset of edges of $G$ \emph{neutral} for the anti-Ramsey number if removing them does not alter the anti-Ramsey number of $G$. Let $k$, $t$, and $n$ be positive integers, and consider $G = kP_4 \cup tP_2$. Assume $S \subseteq E(G)$ consists of internal edges of the $P_4$ components in $G$. It is known that $S$ is neutral when $t \geq k+1 \geq 2$ and $n \geq 8k + 2t - 4$. In this paper, we identify values of $k \geq t$ such that, for all $n$ in a specific subinterval of $[8k + 2t - 4, \infty)$, $S$ remains neutral. Since the anti-Ramsey numbers for matchings are well understood, our results provide a complete determination of the anti-Ramsey number for $G$ under these conditions. Based on our findings, we conjecture that this neutrality may extend to the general case $t \geq 1$, $k \geq 1$, and $n \geq 4k + 2t$, but not when $t = 0$, $k \geq 2$, and $n \geq 4k$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_10676 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On Neutral Edge Sets in Anti-Ramsey Numbers Ghalavand, Ali Jie, Qing Jin, Zemin Li, Xueliang Pan, Linshu Combinatorics The anti-Ramsey number of a graph $G$, introduced by Erdős et al.\ in 1975, is the maximum number of colors in an edge-coloring of the complete graph $K_n$ that avoids a rainbow copy of $G$. We call a subset of edges of $G$ \emph{neutral} for the anti-Ramsey number if removing them does not alter the anti-Ramsey number of $G$. Let $k$, $t$, and $n$ be positive integers, and consider $G = kP_4 \cup tP_2$. Assume $S \subseteq E(G)$ consists of internal edges of the $P_4$ components in $G$. It is known that $S$ is neutral when $t \geq k+1 \geq 2$ and $n \geq 8k + 2t - 4$. In this paper, we identify values of $k \geq t$ such that, for all $n$ in a specific subinterval of $[8k + 2t - 4, \infty)$, $S$ remains neutral. Since the anti-Ramsey numbers for matchings are well understood, our results provide a complete determination of the anti-Ramsey number for $G$ under these conditions. Based on our findings, we conjecture that this neutrality may extend to the general case $t \geq 1$, $k \geq 1$, and $n \geq 4k + 2t$, but not when $t = 0$, $k \geq 2$, and $n \geq 4k$. |
| title | On Neutral Edge Sets in Anti-Ramsey Numbers |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2512.10676 |