The Quest for Triangle-Free Colorings of the Complete Graph

Stanislaw P. Radziszowski
Department of Computer Science
Rochester Institute of Technology


We study the question of whether one can color all the edges of the complete graph K_n with k colors so that monochromatic triangles are avoided. The largest n for which such coloring exists defines the classical multicolor Ramsey number R_k(3). This talk will overview the state of our knowledge of this problem for three and more colors.

An algorithmic approach was successfully used to improve the upper bound and to understand better the best known lower bound 51<=R_4(3). In particular, in a joint work with Susan Fettes, we reproduce the results obtained by Richard Kramer in his amazing unpublished manuscript claiming that R_4(3)<=62.

Colloquia Series page.