Goodness of trees for generalized books (Q1087890)

For any graph \(G\), let \(p(G)\) denote the cardinality of the vertex set of \(G\), let \(\chi(G)\) denote the vertex chromatic number of \(G\) and let \(s(G)\) denote the ''chromatic surplus'' of \(G\), i.e. the smallest number of vertices in a color class under any \(\chi(G)\)-coloring of the vertices of \(G\). For any pair of graphs \(F\) and \(G\), \(r(F,G)\) is the least number \(N\) so that in every 2-coloring of the edges of \(K_N\) either there is a copy of \(F\) with all of its edges in the first color class or a copy of \(G\) with all of its edges in the second color class. It is easy to see that for connected graphs \(F\) and \(G\) with \(p(G)\geq s(F):\) \[ r(F,G)\geq (\chi(F)-1)(p(g)-1)-s(F). \] We say that \(G\) is \(F\)-good if equality holds. The paper is devoted to a study of those graphs \(F\) for which all large trees are \(F\)-good. The results include: All sufficiently large trees are \(K(1,1,m_1,...,M_2)\)-good.