MATH Seminar

Title: Degree Ramsey Numbers of Graphs
Seminar: Combinatorics
Speaker: Kevin Milans of The University of South Carolina
Contact: Dwight Duffus, dwight@mathcs.emory.edu
Date: 2010-10-15 at 4:00PM
Venue: W306
Download Flyer
Abstract: A graph H arrows a graph G if every 2-edge-coloring of H contains a monochromatic copy of G. The degree Ramsey number of G is the minimum k such that some graph with maximum degree k arrows G. Burr, Erdos, and Lovasz found the degree Ramsey number of stars and complete graphs. We establish the degree Ramsey number exactly for double stars and for the cycle on four vertices. We prove that the degree Ramsey number of the n-cycle is at most 96 when n is even and at most 3458 in general. Consequently, there are very sparse graphs that arrow large cycles. We present a family of graphs in which the degree Ramsey number of G is bounded by a function of the maximum degree of G and ask which graph families have this property. This is joint work with Tao Jiang, Bill Kinnersley, and Douglas B. West.