Open AccessExplicit Construction of Small Folkman Graphs
Author(s) -
Linyuan Lü
Publication year - 2008
Publication title -
siam journal on discrete mathematics
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.843
H-Index - 66
eISSN - 1095-7146
pISSN - 0895-4801
DOI - 10.1137/070686743
Subject(s) - combinatorics , mathematics , graph , discrete mathematics , existential quantification , monochromatic color , biology , botany
A Folkman graph is a $K_4$-free graph $G$ such that if the edgesof $G$ are 2-colored, then there exists a monochromatic triangle.Erdös offered a prize for proving the existence of a Folkmangraph with at most 1 million vertices. In this paper, we constructseveral "small" Folkman graphs within this limit. In particular,there exists a Folkman graph on 9697 vertices.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom