科研之友
微信
新浪微博
Facebook
分享链接
摘要
For graphs F and H, we say F is Ramsey for H if every 2-coloring of the edges of F contains a monochromatic copy of H. The graph F is Ramsey H-minimal if F is Ramsey for H and there is no proper subgraph F' of F so that F' is Ramsey for H. Burr et al. defined s(H) to be the minimum degree of F over all Ramsey H-minimal graphs F. Define H-t,H-d to be a graph on t + 1 vertices consisting of a complete graph on t vertices and one additional vertex of degree d. We show that s(H-t,H-d) = d(2) for all values 1 < d < t; it was previously known that s(H-t,H-1) = t - 1, so it is surprising that s(H-t,H-2) = 4 is much smaller. We also make some further progress on some sparser graphs. Fox and Lin observed that s(H) >= 2 delta(H) - 1 for all graphs H, where delta(H) is the minimum degree of H; Szabo et al. investigated which graphs have this property and conjectured that all bipartite graphs H without isolated vertices satisfy s(H) = 2 delta(H) - 1. Fox et al. further conjectured that all connected triangle-free graphs with at least two vertices satisfy this property. We show that d-regular 3-connected triangle-free graphs H, with one extra technical constraint, satisfy s(H) = 2 delta(H) - 1; the extra constraint is that H has a vertex v so that if one removes v and its neighborhood from H, the remainder is connected.
- 出版日期2017-6
- 单位MIT
