A new construction technique of a triangle-free 3-colored K16's
In this paper, we propose a new coloring technique of the edges of the complete graph on 16 vertices, K-16, with three different colors, without producing any monochromatic triangle. This method is totally different from those proposed by [R.E. Greenwood, A.M. Gleason, Combinatorial relations and chromatic graphs, Canadian Journal of Mathematics 7 (1955) 1-7; J.G. Kalbfleish, R.G. Stanton, On the maximal triangle-free edge-chromatic graphs in three colors, Journal of Combinatorial Theory 5 (1968) 9-20; C. Laywine, L.P. Mayberry, A simple construction giving the two non-isomorphic triangle free 3-colored K-16's, Journal of Combinatorial Theory Series B (1988) 120-124; B. Benhamou, Etude des Symetries et de la Cardinalite en Calcul Propoaitionel: Application aux Algorithmes Syntaxiques, Ph.D. Thesis, University of Aix-Marseilles 1, France, 1993] which prove that the classical multicolor Ramsey number R(3,3,3) is 17. This number is the only non-trivial tricolor Ramsey number known till now in spite of more than fifty years of extensive research on Ramsey numbers [S.P. Radziszowski, Small Ramsey numbers, The Electronic Journal of Combinatorics DSI.Revision 11 (2006) 160]. We show also how we can convert the Ramsey-graph 3-coloring problem into a satisfiability instance having 2160 clauses of 3-literals each and 360 variables (i.e., a 3-SAT instance). (c) 2006 Elsevier Inc. All rights reserved.
graph multicolor ramsey number satisfiability