Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings
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_ | 1866910215043022848 |
|---|---|
| author | Ghalavand, Ali Li, Xueliang |
| author_facet | Ghalavand, Ali Li, Xueliang |
| contents | A subgraph in an edge-colored graph is called rainbow if all its edges have distinct colors. For a graph $G$ and an integer $n$, the anti-Ramsey number $AR(n,G)$ is the maximum number of colors in an edge-coloring of $K_n$ that contains no rainbow copy of $G$. We study $AR(n, kP_3 \cup tP_2)$, where $kP_3 \cup tP_2$ is the linear forest of $k$ disjoint paths on three vertices and a matching of size $t$. Recently, Jie and Jin [Discrete Appl. Math. 386 (2026) 30-57] determined this number for $k\geq 2$, $t\geq\frac{k^2-3k+4}{2}$ and $n=2t+3k$. Here we solve the spanning case $n=3k+2t$ for all $k\ge1$, $t\ge2$ with no extra restrictions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_25949 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings Ghalavand, Ali Li, Xueliang Combinatorics A subgraph in an edge-colored graph is called rainbow if all its edges have distinct colors. For a graph $G$ and an integer $n$, the anti-Ramsey number $AR(n,G)$ is the maximum number of colors in an edge-coloring of $K_n$ that contains no rainbow copy of $G$. We study $AR(n, kP_3 \cup tP_2)$, where $kP_3 \cup tP_2$ is the linear forest of $k$ disjoint paths on three vertices and a matching of size $t$. Recently, Jie and Jin [Discrete Appl. Math. 386 (2026) 30-57] determined this number for $k\geq 2$, $t\geq\frac{k^2-3k+4}{2}$ and $n=2t+3k$. Here we solve the spanning case $n=3k+2t$ for all $k\ge1$, $t\ge2$ with no extra restrictions. |
| title | Anti-Ramsey Numbers for Spanning Linear Forests of 3-Vertex Paths and Matchings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2509.25949 |