pith. sign in

arxiv: 2605.26826 · v2 · pith:LKLNJ6JZnew · submitted 2026-05-26 · 🧮 math.CO

Ramsey goodness of complete multipartite graphs with one large part

classification 🧮 math.CO
keywords alphaldotsgoodgraphlargecompletegraphspartite
0
0 comments X
read the original abstract

For graph $G$, a connected graph $H$ of order $n$ is $G$-good if $r(G,H)=(\chi(G)-1)(n-1)+s(G)$, where $\chi(G)$ is the chromatic number of $G$ and $s(G)$ is the minimum size of a color class in a $\chi(G)$-coloring of $G$. Let $K_{\alpha_{1},\ldots ,\alpha_{p},n}$ be the complete $(p+1)$-partite graph with partite sets of sizes $\alpha_1,\ldots,\alpha_p,n$. Burr, Faudree, Rousseau and Schelp (1983) showed that $K_{\alpha_1,\ldots,\alpha_p,n}$ are $(K_2+mK_1)$-good for large $n$. We determine graphs $G$ such that $K_{\alpha_{1},\ldots ,\alpha_{p},n}$ are $G$-good for large $n$. The characterization depends on $\mathrm{snd}(\alpha_i)$, the smallest non-divisor of $\alpha_i$, where $1\le i\le p$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.