Premium
Coloring the edges of k m × k m
Author(s) -
Heinrich Katherine
Publication year - 1990
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190140509
Subject(s) - combinatorics , mathematics , integer (computer science) , van der waerden's theorem , graph , square (algebra) , constant (computer programming) , discrete mathematics , geometry , computer science , programming language
In the graph K m × K m a 4‐cycle is called square if its vertices do not all lie in the same copy of K m . A c ‐coloring of the edges of K m × K m is good if in any square 4‐cycle the two edges of at least one nonadjacent pair receive different colors. Let f (2, c ) denote the smallest integer m so that no c ‐coloring of K m × K m is good. We show that there exists a constant k so that f (2, c ) > kc 3 . (This function was introduced by Shelah in his proof of van der Waerden's theorem).