Let $m,n \ge 2$ be such that $m-1$ is a divisor of $n-1$. Let $T$ be a tree with $m$ vertices. Calculate the Ramsey number $R(T,K_{1,n})$.
Thoughts: I'm having trouble approaching this question. I think the detail about the divisibility is somehow related to the fact that $n-1$ is the number of nodes on one side of the bipartite graph. $m-1$ is the number of nodes in a tree excluding some defined "root". I'd love some ideas on what to consider and how to approach such a question. My main problem is that I don't know what to do with the info about divisibility and forms of the two possible subgraphs. I'm wondering if there is some way to connect this to Chvátal's Theorem on $R(T,K_n)$.
Suppose you have the graph $G = \left(\frac{n-1}{m-1}+1\right)\times K_{m-1}$
Then $T_m$ is not in $G$, and $K_{1,n}$ is not in $\bar{G}$.
Since the order of $G$ is $n+m-2$, the Ramsay number is $\geq n+m-1$.
I'd be willing to bet that it's in fact equal to $n+m-1$, since any vertex added to $G$ would appear to create an edge into $K_{m-1}$ which will include $T_m$, or will have no edge into at least $n$ vertices of $G$.
Edit: actually, if $G$ is a graph with $n+m-1$ vertices that does not contain any $K_{1,n}$, then each vertex contains at most $n-1$ edges, so $\bar{G}$ has at least $m-1$ edges.
Then there's a theorem which says that any tree of order $m$ must be a subgraph of any graph $G$ with $\delta(G)\geq m-1$ (i.e. Minimum degree of the vertices of $G$ is $\geq m-1$).
This result can be proven quite simply by induction.