This paper explores the Ramsey-good property for star and fan graphs with implications for Hajós graphs.
Given two graphs G₁ and G₂, the Ramsey number R(G₁,G₂) denotes the smallest integer N such that any red-blue coloring of the edges of KN contains either a red G₁ or a blue G₂. Let G₁ be a graph with chromatic number $χ$ and chromatic surplus s, and let G₂ be a connected graph with n vertices. The graph G₂ is said to be Ramsey-good for the graph G₁ (or simply G₁-good) if, for n ≥ s, \[R(G_1,G_2)=(χ-1)(n-1)+s.\] The G₁-good property has been extensively studied for star-like graphs when G₁ is a graph with χ(G₁)≥ 3, as seen in works by Burr-Faudree-Rousseau-Schelp (J. Graph Theory, 1983), Li-Rousseau (J. Graph Theory, 1996), Lin-Li-Dong (European J. Combin., 2010), Fox-He-Wigderson (Adv. Combin., 2023), and Liu-Li (J. Graph Theory, 2025), among others. However, all prior results require G₁ to have chromatic surplus $1$. In this paper, we extend this investigation to graphs with chromatic surplus 2 by considering the Hajós graph Hₐ. For a star K1,n, we prove that K1,n is Hₐ-good if and only if n is even. For a fan Fₙ with n≥ 111, we prove that Fₙ is Hₐ-good.
No takes yet. Share an insight, caveat, or question.
He et al. (2025) studied this question.
Synapse has enriched 5 closely related papers on similar clinical questions. Consider them for comparative context: