Resource title

Planar Ramsey numbers

Resource image

image for OpenScout resource :: Planar Ramsey numbers

Resource description

The planar Ramsey number PR(k, l) (k, l ≥ 2) is the smallest integer n such that any planar graph on n vertices contains either a complete graph on k vertices or an independent set of size l. We find exact values of PR(k, l) for all k and l. Included is a proof of a 1976 conjecture due to Albertson, Bollobás, and Tucker that every triangle-free planar graph on n vertices contains an independent set of size left floorn/3right floor + 1.

Resource author

Resource publisher

Resource publish date

Resource language

en

Resource content type

Resource resource URL

http://eprints.lse.ac.uk/23593/

Resource license