Premium
The maximum number of K 3 ‐free and K 4 ‐free edge 4‐colorings
Author(s) -
Pikhurko Oleg,
Yilma Zelealem B.
Publication year - 2012
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/jdr031
Subject(s) - monochromatic color , combinatorics , mathematics , enhanced data rates for gsm evolution , graph , discrete mathematics , physics , computer science , optics , telecommunications
Let F ( n, r, k ) denote the maximum number of edge r ‐colorings without a monochromatic copy of K k that a graph with n vertices can have. Addressing two questions left open by Alon, Balogh, Keevash and Sudakov [ J. London Math. Soc. 70 (2004) 273–288], we determine F ( n , 4, 3) and F ( n , 4, 4) and describe the extremal graphs for all large n .