Jiafu He ; Haiyu Zeng ; Yanbo Zhang - Ramsey goodness of stars and fans for the Hajós graph

dmtcs:15817 - Discrete Mathematics & Theoretical Computer Science, September 20, 2025, vol. 27:3 - https://doi.org/10.46298/dmtcs.15817
Ramsey goodness of stars and fans for the Hajós graphArticle

Authors: Jiafu He ; Haiyu Zeng ; Yanbo Zhang

    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 \ge 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)\ge 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\ge 111$, we prove that $F_n$ is $H_a$-good.


    Volume: vol. 27:3
    Section: Graph Theory
    Published on: September 20, 2025
    Accepted on: September 8, 2025
    Submitted on: June 10, 2025
    Keywords: Combinatorics, 05C55, 05D10

    Consultation statistics

    This page has been seen 368 times.
    This article's PDF has been downloaded 160 times.