Ramsey goodness of stars and fans for the Hajós graph

Jiafu He; Haiyu Zeng; Yanbo Zhang

doi:10.46298/dmtcs.15817

paper

Ramsey goodness of stars and fans for the Hajós graph

arXiv:2506.06724 · doi:10.46298/dmtcs.15817

Abstract

Given two graphs $G_{1}$ and $G_{2}$ , the Ramsey number $R (G_{1}, G_{2})$ denotes the smallest integer $N$ such that any red-blue coloring of the edges of $K_{N}$ contains either a red $G_{1}$ or a blue $G_{2}$ . Let $G_{1}$ be a graph with chromatic number $χ$ and chromatic surplus $s$ , and let $G_{2}$ be a connected graph with $n$ vertices. The graph $G_{2}$ is said to be Ramsey-good for the graph $G_{1}$ (or simply $G_{1}$ -good) if, for $n \geq s$ , \[R(G_1,G_2)=(χ-1)(n-1)+s.\] The $G_{1}$ -good property has been extensively studied for star-like graphs when $G_{1}$ is a graph with $χ (G_{1}) \geq 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_{1}$ 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_{a}$ . For a star $K_{1, n}$ , we prove that $K_{1, n}$ is $H_{a}$ -good if and only if $n$ is even. For a fan $F_{n}$ with $n \geq 111$ , we prove that $F_{n}$ is $H_{a}$ -good.