Details

Autor(en) / Beteiligte

• Fang, Chunqiu
• Győri, Ervin
• Xiao, Jimeng

Titel

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

Ist Teil von

• Graphs and combinatorics, 2021-11, Vol.37 (6), p.2287-2304

Ort / Verlag

Tokyo: Springer Japan

Erscheinungsjahr

2021

Link zum Volltext

Quelle

Alma/SFX Local Collection

Beschreibungen/Notizen

• 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 ex ( 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 , 3 ) .