Anti-Ramsey problems for cycles

Jiale Xu, Mei Lu and Ke Liu

Applied Mathematics and Computation, 2021, vol. 408, issue C

Abstract: We call a subgraph of an edge-colored graph rainbow, if all of its edges have different colors. A rainbow copy of a graph H in an edge-colored graph G is a subgraph of G isomorphic to H such that the coloring restricted to this subgraph is a rainbow coloring. Given two graphs G and H, let Ar(G,H) denote the maximum number of colors in a coloring of the edges of G that has no any rainbow copy of H. When G is Kn, Ar(G,H) is called the anti-Ramsey number. Anti-Ramsey number was introduced by Erdös, Simonovits and Sós in the 1970s. Since then, the field has blossomed in a wide variety of papers and some other graphs were used as host graphs. In this paper, we give a new method to compute the anti-Ramsey number by constructing a corresponding hypergraph. As application, we determine the exact values of Ar(G,Ck) when the host graph G is Wd, Pm×Pn, Pm×Cn, Cm×Cn and cyclic Cayley graph, respectively.

Keywords: Hypergraph; Rainbow; Anti-Ramsey problem; Cycle (search for similar items in EconPapers)
Date: 2021
References: View complete reference list from CitEc
Citations: View citations in EconPapers (3)

Downloads: (external link)
http://www.sciencedirect.com/science/article/pii/S0096300321004343
Full text for ScienceDirect subscribers only

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:eee:apmaco:v:408:y:2021:i:c:s0096300321004343

DOI: 10.1016/j.amc.2021.126345

Access Statistics for this article

Applied Mathematics and Computation is currently edited by Theodore Simos

More articles in Applied Mathematics and Computation from Elsevier
Bibliographic data for series maintained by Catherine Liu ().