Originators: S.A. Burr, P. Erdős, L. Lovász (presented by Bill Kinnersley - REGS 2008)
Definitions: For graphs G and H, we say that H → G if every 2-edge-coloring of H contains a monochromatic copy of G. We say that H is Ramsey-minimal for G if H → G but H has no proper subgraph H' such that H' → G. Let s(G) denote the minimum of δ(H) over all H that are Ramsey-minimal for G. The Ramsey number R(G) is the minimum n such that Kn→ G.
Background: It is easily shown that 2δ(G)-1 ≤ s(G) ≤ R(G)-1 (for the lower bound, if δH(v)<2δ(G)-1, then H-v → G, since otherwise a 2-coloring of E(H-v) with no monochromatic G can be augmented to a such a 2-coloring of E(H)).
Question 1: When does s(G)=2δ(G)-1 hold?
Comments: Fox and Lin [FL] showed that if a ≤ b, then s(Ka,b) = 2a-1. Szabó, Zumstein, and Zürcher [SZZ] later showed that s(G) = 2δ(G)-1 for many more bipartite graphs, including paths, even cycles, and trees. Their result states that s(G)=2δ(G)-1 when G is a bipartite graph if in some partite set containing a vertex of minimum degree the number of vertices with degree larger than δ(G) is less than the total number of vertices in the other partite set. This applies to trees (easy), to bipartite graphs where each partite set contains a vertex of minimum degree, and to more.
Burr, Erdős, and Lovász [BEL] showed that s(Kn)=(n-1)2 (see [FL] for an alternative proof). Little else is known about s(G) for non-bipartite G.
Question 2: Can s(G) be bounded above in terms of δ(G) for bipartite G?
Comments: There is no such bound for non-bipartite graphs; if G is a large complete graph plus an independent edge, then δ(G)=1, but s(G) can be arbitrarily large [SZZ].
Definition: When we use r colors instead of just two, the analogous parameter is written as s(G;r).
Question 3: What can be said about s(G;r)?
Comments: As before, easily rδ(G)-r+1 ≤ s(G;r) ≤ R(G;r)-1. [FL] notes that the proof of their result on complete bipartite graphs generalizes to r colors: s(Ka,b;r)=ra-r+1 (when a≤b). Nothing else seems to be known about s(G;r).
References:
[BEL] Burr, S. A.; Erdős, P.; Lovász, L.
On graphs of Ramsey type.
Ars Combinatoria 1 (1976), no. 1, 167--190.
[FL] Fox, Jacob; Lin, Kathy.
The minimum degree of Ramsey-minimal graphs.
J. Graph Theory 54 (2007), no. 2, 167--177.
[SZZ] Szabó, T.; Zumstein, P.; Zürcher, S. Slides from a talk at
Mittagseminar ETH Zürich.
http://www.inf.ethz.ch/personal/zuphilip/talks/MinRamsey.pdf