REAL

On the Maximal Colorings of Complete Graphs Without Some Small Properly Colored Subgraphs

Fang, Chunqiu and Győri, Ervin and Xiao, Jimeng (2021) On the Maximal Colorings of Complete Graphs Without Some Small Properly Colored Subgraphs. GRAPHS AND COMBINATORICS, 37 (6). pp. 2287-2304. ISSN 0911-0119

[img]
Preview
Text
s00373-021-02351-4.pdf - Published Version
Available under License Creative Commons Attribution.

Download (375kB) | Preview

Abstract

Let pr(K-n, G) be the maximum number of colors in an edge-coloring of K-n with no properly colored copy of G. For a family F of graphs, let e(x) (n, F) be the maximum number of edges in a graph G on n vertices which does not contain any graphs in F as subgraphs. In this paper, we show that pr(K-n, G) - ex(n, G') = o(n(2)), where G' = {G - M : M is a matching of G}. Furthermore, we determine the value of pr(K-n, P-l) for sufficiently large n and the exact value of pr(K-n, G), where G is C-5, C-6 and K-4(-), respectively. Also, we give an upper bound and a lower bound of pr(K-n, K-2,K-3).

Item Type: Article
Uncontrolled Keywords: Turán numbers; Anti-Ramsey numbers; Properly colored subgraphs;
Subjects: Q Science / természettudomány > QA Mathematics / matematika
SWORD Depositor: MTMT SWORD
Depositing User: MTMT SWORD
Date Deposited: 17 Jul 2025 18:41
Last Modified: 17 Jul 2025 18:41
URI: https://real.mtak.hu/id/eprint/221244

Actions (login required)

Edit Item Edit Item