On graphs \(G\) for which all large trees are \(G\)-good (Q1313348): Difference between revisions

If \(G\) is a graph with chromatic number \(k\), then the `chromatic surplus' of \(G\) is the largest number \(s\) such that every proper \(k\)-coloring of \(G\)'s vertices admits, for each of the \(k\) colors, \(s\) vertices of that color. In the previous paper [J. Lond. Math. Soc., II. Ser. 24, 405-413 (1981; Zbl 0474.05051)] the first author proved that if \(G\) is a graph with chromatic number \(k\) and surplus \(s\), and if \(H\) is a connected graph on \(n\) vertices, where \(n\geq s\), then the generalized Ramsey number \(r(G,H)\) satisfies \(r(G,H) \geq (k-1)(n-1)+s\). In this paper, the case \(s=1\) is examined closely. It is proven that there are two sets of multipartite graphs \(L(k,m)\) and \(M(k,m)\), \(k= 1,2,\dots\) and \(m=1,2,\dots\), such that the following are equivalent for each graph \(G\): I. The chromatic number of \(G\) is \(k\) and for some \(m\), \(G\) is a subgraph of both \(L(k,m)\) and \(M(k,m)\). II. For sufficiently large \(n\), every \(n\)-vertex tree \(H\) satisfies \(r(G,H)=(k-1)(n-1)+1\).