
Discrete Mathematics and Optimization Seminar

Nov. 5, 2008
MC 320, 4:00 PM
On the Minimum Degree of Ramsey Minimal Graphs
Philipp Zumstein
ETH Zürich

A graph G is called HRamsey if in every edgecoloring of G with colors red and blue there is a monochromatic copy of H. Furthermore, if every proper subgraph G' of G is not HRamsey, then we say that G is Hminimal. We are interested in the minimum of the minimum degree over all Hminimal graphs and denote this parameter with s(H).
If you would instead look at the minimum number of vertices (edges) in a Hminimal graph, then this is exactly the classical Ramsey number (size Ramsey number).
We calculate s(H) for all H from a big class of bipartite graphs including paths, even cycles, regular connected bipartite graphs, and trees. Another question we look at is how big can s(H) be for H a graph with minimum degree equal to 1.



