betaFeedback

WorksMathematics

Ramsey goodness of large generalized fans

Abstract

Given graphs GG and HH, the Ramsey number r(G,H)r(G,H) is the smallest integer NN such that any red-blue edge coloring of KNK_N contains a red copy of GG or a blue copy of HH. If HH is connected, Burr's lower bound gives r(G,H)≥(χ(G)−1)(∣V(H)∣−1)+s(G)r(G,H)\geq (χ(G)-1)(|V(H)|-1)+s(G), where s(G)s(G) is the minimum size of a color class over all proper χ(G)χ(G)-colorings of GG. The graph HH is called GG-good if equality holds in this bound. Liu and Li [J. Graph Theory, 2025] characterized the graphs GG with s(G)=1s(G)=1 for which Kp+nHK_p+nH is GG-good for p≥2p\geq 2 and sufficiently large nn, and posed the corresponding problem for p=1p=1. We solve this problem by showing that for a graph GG with χ(G)=k+1≥2χ(G)=k+1\geq 2 and s(G)=1s(G)=1, a graph HH of order hh and sufficiently large nn, K1+nHK_1+nH is GG-good if and only if G⊆mK2+Kk−1(m)G\subseteq mK_2+K_{k-1}(m) when nhnh is odd, or G⊆(mK2∪K1,2)+Kk−1(m)G\subseteq (mK_2\cup K_{1,2})+K_{k-1}(m) when nhnh is even, for some positive integer mm.

Paper details

vlnc:W_42w7fnb3
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
arXiv nonexclusive license
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

ChatGPT (OpenAI)

View statement
Looking for related papers…