A new construction technique of a triangle-free 3-colored K16’s

QSpace/Manakin Repository

A new construction technique of a triangle-free 3-colored K16’s

Show simple item record


dc.contributor.author Jaam, Jihad Mohamad
dc.date.accessioned 2009-12-30T05:59:39Z
dc.date.available 2009-12-30T05:59:39Z
dc.date.issued 2006-12-03
dc.identifier.citation Volume 177, Issue 9, 1 May 2007, Pages 1992-1995 en_US
dc.identifier.uri http://dx.doi.org/10.1016/j.ins.2006.12.002
dc.identifier.uri http://hdl.handle.net/10576/10577
dc.description.abstract In this paper, we propose a new coloring technique of the edges of the complete graph on 16 vertices, K16, 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 K16’s, Journal of Combinatorial Theory Series B (1988) 120–124; B. Benhamou, Étude des Symétries et de la Cardinalité 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). en_US
dc.language.iso en en_US
dc.subject Multicolor Ramsey number en_US
dc.subject Satisfiability en_US
dc.subject Graph en_US
dc.title A new construction technique of a triangle-free 3-colored K16’s en_US
dc.type Article en_US

Files in this item

Files Size Format View Description
construction technique.pdf 126.3Kb PDF View/Open A new construction technique of a triangle-free 3-colored K16’s

This item appears in the following Collection(s)

Show simple item record

Search QSpace


Advanced Search

Browse

My Account