×

Planar Ramsey numbers. (English) Zbl 0794.05091

The planar Ramsey number \(\text{PR}(k,\ell)\) \((k,\ell\geq 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 \(\ell\). We find exact values of \(\text{PR}(k,\ell)\) for all \(k\) and \(\ell\). 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 \(\bigl\lfloor{n\over 3}\bigr\rfloor+1\).

MSC:

05C55 Generalized Ramsey theory
PDFBibTeX XMLCite
Full Text: DOI