Ramsey goodness and generalized stars

2010 
Let G and H be fixed graphs with s(G)=s (the minimum number of vertices in a color class over all proper vertex-colorings of G with @g(G) colors). It is shown that r(K"1+G,K"1+nH)@?k(hn+s-1)+1 for large n, where @g(G)=k>=2. In particular, if s is odd or s is even and hn is odd, then r(K"1+K"k(s),K"1+nH)=k(hn+s-1)+1, where K"k(s) is a complete k-partite graph with s vertices in each part, implying that K"1+nH is not (K"1+K"k(s))-good. Moreover, r(K"1+sK"2,K"1+nH)=2hn+1 for large n.
    • Correction
    • Source
    • Cite
    • Save
    • Machine Reading By IdeaReader
    13
    References
    14
    Citations
    NaN
    KQI
    []