PreprintCC BY 4.0arXiv
Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
Abstract
The anti-Ramsey number AR(n,F) is the maximum number of colors in an edge-coloring of the complete graph Kn containing no rainbow copy of F. I prove that every spanning linear forest on an even number n≥6 of vertices whose components have even orders and which has an isolated edge has the same anti-Ramsey number as a perfect matching on n vertices. The orders of the longer path components may be different.
Related
- Counting Near-Spanning Matchings in Latin Squares and Steiner Triple Systems
- A simplified proof of the FPRAS for counting perfect matchings
- Perfect matchings in hypergraphs and Feige's inequality
- Covering Bridgeless Claw-Free Cubic Graphs with Perfect Matchings
- The Cycle Rank Threshold: Perfect Matchings and Bipartite Parter Graphs
BibTeX
@misc{ghalavand2026spanning,
title = {{Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings}},
author = {Ali Ghalavand},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.11441},
eprint = {2610.11441},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.11441},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Spanning Even Linear Forests with Isolated Edges Share the Anti-Ramsey Numbers of Perfect Matchings
AU - Ali Ghalavand
PY - 2026
DA - 2026/10/08
PB - arXiv
DO - 10.48550/arxiv.2610.11441
UR - https://arxiv.org/abs/2610.11441
AB - The anti-Ramsey number AR(n,F) is the maximum number of colors in an edge-coloring of the complete graph K_n containing no rainbow copy of F. I prove that every spanning linear forest on an even number n≥6 of vertices whose components have even orders and which has an isolated edge has the same anti-Ramsey number as a perfect matching on n vertices. The orders of the longer path components may be different.
ER -