Rainbow short linear forests in edge-colored complete graph

An edge-colored graph G is called rainbow if no two edges of G have the same color. For a graph G and a subgraph H⊆G, the anti-Ramsey number AR(G,H) is the maximum number of colors in an edge-coloring of G such that G contains no rainbow copy of H. Recently, the anti-Ramsey problem for disjoint unio...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2025-01, Vol.361, p.523-536
Main Authors: He, Menglu, Jin, Zemin
Format: Article
Language:English
Subjects:
Anti-Ramsey number
Matching
Path
Rainbow graph
Citations: Items that this one cites
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:An edge-colored graph G is called rainbow if no two edges of G have the same color. For a graph G and a subgraph H⊆G, the anti-Ramsey number AR(G,H) is the maximum number of colors in an edge-coloring of G such that G contains no rainbow copy of H. Recently, the anti-Ramsey problem for disjoint union of graphs received much attention. In particular, several researchers focused on the problem for graphs consisting of small components. In this paper, we continue the work in this direction. We refine the bound and obtain the precise value of AR(Kn,P3∪tP2) for all n≥2t+3. Additionally, we determine the value of AR(Kn,2P3∪tP2) for any integers t≥1 and n≥2t+7.
ISSN:0166-218X
DOI:10.1016/j.dam.2024.11.002