Paper Info
Title
A new construction technique of a triangle-free 3-colored K16's
Abstract
In this paper, we propose a new coloring technique of the edges of the complete graph on 16 vertices, K"1"6, 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"1"6'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 I, 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 DS1.Revision 11 (2006) 1-60]. 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).
Year
DOI
Venue
2007
10.1016/j.ins.2006.12.002
Inf. Sci.
Keywords
Field
DocType
small ramsey number,combinatorial theory,combinatorial relation,ramsey number,3-colored k16,combinatorial theory series b,non-trivial tricolor ramsey number,electronic journal,canadian journal,3-sat instance,ramsey number r,new construction technique,satisfiability,graph,complete graph
Ramsey theory,Complete graph,Discrete mathematics,Graph,Combinatorics,Colored,Vertex (geometry),Satisfiability,Ramsey's theorem,Monochromatic triangle,Mathematics
Journal
Volume
Issue
ISSN
177
9
0020-0255
Citations 
PageRank 
References 
0
0.34
3
Authors
1
Name
Order
Citations
PageRank
Jihad Mohamad Jaam1737.14