|
|
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 H-Ramsey if in every edge-coloring of G with colors red and blue there is a monochromatic copy of H. Furthermore, if every proper subgraph G' of G is not H-Ramsey, then we say that G is H-minimal. We are interested in the minimum of the minimum degree over all H-minimal graphs and denote this parameter with s(H).
If you would instead look at the minimum number of vertices (edges) in a H-minimal 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.
|
|
|
|