Proof of a conjecture on fractional Ramsey numbers

Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function rf (a1, a2, …, ak) 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 determinin...

Full description

Saved in:
Bibliographic Details
Published in:Journal of graph theory 2010-02, Vol.63 (2), p.164-178
Main Authors: Brown, Jason, Hoshino, Richard
Format: Article
Language:English
Subjects:
chromatic number
circulant graph
circular chromatic number
fractional chromatic number
independence number
integer distance graph
Ramsey theory
star extremal
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Jacobson, Levin, and Scheinerman introduced the fractional Ramsey function rf (a1, a2, …, ak) 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
ISSN:0364-9024
1097-0118
DOI:10.1002/jgt.20416