Anti-Ramsey Number for Suspension of Edge-Critical Graphs
Abstract
An edge-colored graph is called a rainbow graph if all its edges have distinct colors. The \textit{anti-Ramsey number}, denoted by ar(n,F), for a fixed graph F and a positive integer n, is the maximum number of colors used in an edge-coloring of the complete graph Kn that contains no rainbow copy of F. Meanwhile, the \textit{Turán number}, denoted by ex(n,F), for graph F and n, is the maximum number of edges in an n-vertex graph that does not contain F as a subgraph. For a vertex v and a multiset ℋ of graphs, the \textit{suspension} ℋ + v of ℋ is the graph obtained by connecting the vertex v to all vertices of H for each H ∈ ℋ. Let integers k≥ 1 and r≥ 2 be fixed, and suppose that ℋk+1={H1, H2, …, Hk+1}+v satisfying H1, H2, …, Hk+1 are pairwise vertex-disjoint edge-critical graphs, and χ(Hi)=r for i=1,2,…, k+1.In this paper, we determine $ \ar(n,\mathcal{H}_{k+1}) $ for k≥ 1, r≥ 2 and sufficiently large n. This result unifies and generalizes a result of Liu et al. (arXiv:2411.08475) concerning the friendship graph, and a result of Lu et al. (arXiv:2507.13165) on the intersecting cliques.
Related
BibTeX
@misc{li2026antiramsey,
title = {{Anti-Ramsey Number for Suspension of Edge-Critical Graphs}},
author = {Shuchao Li and Haojie Zheng},
howpublished = {arXiv},
year = {2026},
month = aug,
doi = {10.48550/arxiv.2608.29525},
eprint = {2608.29525},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.29525},
}
RIS
TY - UNPB
TI - Anti-Ramsey Number for Suspension of Edge-Critical Graphs
AU - Shuchao Li
AU - Haojie Zheng
PY - 2026
DA - 2026/08/30
PB - arXiv
DO - 10.48550/arxiv.2608.29525
UR - https://arxiv.org/abs/2608.29525
AB - An edge-colored graph is called a rainbow graph if all its edges have distinct colors. The \textit{anti-Ramsey number}, denoted by ar(n,F), for a fixed graph F and a positive integer n, is the maximum number of colors used in an edge-coloring of the complete graph K_n that contains no rainbow copy of F. Meanwhile, the \textit{Turán number}, denoted by ex(n,F), for graph F and n, is the maximum number of edges in an n-vertex graph that does not contain F as a subgraph. For a vertex v and a multiset ℋ of graphs, the \textit{suspension} ℋ + v of ℋ is the graph obtained by connecting the vertex v to all vertices of H for each H ∈ ℋ. Let integers k≥ 1 and r≥ 2 be fixed, and suppose that ℋ_k+1={H_1, H_2, …, H_k+1}+v satisfying H_1, H_2, …, H_k+1 are pairwise vertex-disjoint edge-critical graphs, and χ(H_i)=r for i=1,2,…, k+1.In this paper, we determine $ \ar(n,\mathcal{H}_{k+1}) $ for k≥ 1, r≥ 2 and sufficiently large n. This result unifies and generalizes a result of Liu et al. (arXiv:2411.08475) concerning the friendship graph, and a result of Lu et al. (arXiv:2507.13165) on the intersecting cliques.
ER -