Premium
Proof of a conjecture on fractional Ramsey numbers
Author(s) -
Brown Jason,
Hoshino Richard
Publication year - 2010
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20416
Subject(s) - mathematics , combinatorics , ramsey's theorem , conjecture , generalization , ramsey theory , circulant matrix , discrete mathematics , integer (computer science) , circulant graph , graph , line graph , mathematical analysis , voltage graph , computer science , programming language
Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function r f ( a 1 , a 2 , …, a k ) as an extension of the classical definition for Ramsey numbers. They determined an exact formula for the fractional Ramsey function for the case k =2. In this article, we answer an open problem by determining an explicit formula for the general case k >2 by constructing an infinite family of circulant graphs for which the independence numbers can be computed explicitly. This construction gives us two further results: a new (infinite) family of star extremal graphs which are a superset of many of the families currently known in the literature, and a broad generalization of known results on the chromatic number of integer distance graphs. © 2009 Wiley Periodicals, Inc. J Graph Theory 63: 164–178, 2010