Pim van 't Hof

Graph classes and Ramsey numbers

Rémy Belmonte, Pinar Heggernes, Pim van 't Hof, Arash Rafiey and Reza Saei

Discrete Applied Mathematics, vol. 173, pp. 16-27, 2014.
[DOI][Preprint]

A preliminary version of this paper, entitled "Ramsey numbers for line graphs and perfect graphs", appeared in the proceedings of COCOON 2012, the 18th Annual International Computing and Combinatorics Conference (held on August 20-22, 2012 in Sydney, Australia), Lecture Notes in Computer Science, vol. 7434, pp. 204-215, 2012. This preliminary version received the best paper award at COCOON 2012.
[DOI] [Slides]

Abstract:

For any graph class ℌ and any two positive integers i and j, the Ramsey number R_ℌ(i,j) is the smallest positive integer such that every graph in ℌ on at least R_ℌ(i,j) vertices has a clique of size i or an independent set of size j. For the class of all graphs, Ramsey numbers are notoriously hard to determine, and the exact values are known only for very small values of i and j. For planar graphs, a formula for determining all Ramsey numbers was obtained by Steinberg and Tovey (J. Comb. Theory Ser. B 59 (1993), 288-296). On the other hand, it is highly unlikely that such a formula will ever be found for claw-free graphs, as there exist infinitely many nontrivial Ramsey numbers for claw-free graphs that are as difficult to determine as for arbitrary graphs. Inspired by this contrast between known results on planar graphs and claw-free graphs, we initiate a systematic study of Ramsey numbers for graph classes. We give exact formulas for determining all Ramsey numbers for the class of perfect graphs and many of its subclasses. We also establish all Ramsey numbers for line graphs and long circular interval graphs, identified by Chudnovsky and Seymour as "the two principal basic classes of claw-free graphs", as well as for fuzzy circular interval graphs, another important subclass of claw-free graphs that contains all long circular interval graphs. As complementary results, we determine all Ramsey numbers for circular-arc graphs and cactus graphs.