Computing the Folkman number F_v(2,2,3;4)

Show simple item record

dc.contributor.author Coles, Jonathan
dc.contributor.author Radziszowski, Stanislaw
dc.date.accessioned 2009-01-09T20:11:03Z
dc.date.available 2009-01-09T20:11:03Z
dc.date.issued 2006
dc.identifier.citation Journal of Combinatorial Mathematics and Combinatorial Computing 58 (2006) 13-22
dc.identifier.uri http://hdl.handle.net/1850/7993
dc.description.abstract We discuss a branch of Ramsey theory concerning vertex Folkman numbers and how computer algorithms have been used to compute a new Folkman number. We write G ! (a1, . . . , ak)v if for every vertex k-coloring of an undirected simple graph G, a monochromatic Kai is forced in color i 2 {1, . . . , k}. The vertex Folkman number is defined as Fv(a1, . . . , ak; p) = min{|V (G)| : G ! (a1, . . . , ak)v ^ Kp 6 G}. Folkman showed in 1970 that this number exists for p > max{a1, . . . , ak}. Let m = 1+Pk i=1(ai−1) and a = max{a1, . . . , ak}, then Fv(a1, . . . , ak; p) = m for p > m, and Fv(a1, . . . , ak; p) = a +m for p = m. For p < m the situation is more difficult and much less is known. We show here that, for a case of p = m−1, Fv(2, 2, 3; 4) = 14.
dc.language.iso en_US
dc.publisher The Charles Babbage Research Centre: Journal of Combinatorial Mathematics and Combinatorial Computing
dc.relation.ispartofseries vol. 58
dc.relation.ispartofseries pps. 13-22
dc.subject Folkman numbers
dc.subject Ramsey numbers
dc.subject Vertex
dc.title Computing the Folkman number F_v(2,2,3;4)
dc.type Article

Files in this item

Files Size Format View
SRadziszowskiArticle2006.pdf 379.7Kb PDF View/Open

This item appears in the following Collection(s)

Show simple item record

Search RIT DML


Advanced Search

Browse