Paper Info
Title
Graph classes and Ramsey numbers.
Abstract
For a graph class G and any two positive integers i and j, the Ramsey number RG(i,j) is the smallest positive integer such that every graph in G on at least RG(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 they are known only for very small values of i and j. Even if we restrict G to be the class of claw-free graphs, it is highly unlikely that a formula for determining RG(i,j) for all values of i and j will ever be found, as there are infinitely many nontrivial Ramsey numbers for claw-free graphs that are as difficult to determine as for arbitrary graphs. Motivated by this difficulty, we establish here exact formulas for all Ramsey numbers for three important subclasses of claw-free graphs: line graphs, long circular interval graphs, and fuzzy circular interval graphs. On the way to obtaining these results, we also establish all Ramsey numbers for the class of perfect graphs. Such positive results for graph classes are rare: a formula for determining RG(i,j) for all values of i and j, when G is the class of planar graphs, was obtained by Steinberg and Tovey (1993), and this seems to be the only previously known result of this kind. We complement our aforementioned results by giving exact formulas for determining all Ramsey numbers for several graph classes related to perfect graphs.
Year
DOI
Venue
2014
10.1016/j.dam.2014.03.016
Discrete Applied Mathematics
Keywords
Field
DocType
Graph classes,Ramsey numbers,Claw-free graphs,Perfect graphs
Discrete mathematics,Combinatorics,Indifference graph,Chordal graph,Clique-sum,Ramsey's theorem,Cograph,Pathwidth,Mathematics,Triangle-free graph,Split graph
Journal
Volume
ISSN
Citations 
173
0166-218X
1
PageRank 
References 
Authors
0.35
12
5
Name
Order
Citations
PageRank
Rémy Belmonte17411.76
Pinar Heggernes284572.39
Pim van 't Hof320920.75
Arash Rafiey411.03
Reza Saei5243.62