Goodness of trees for generalized books

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.

Recommendations

Cites work

Cited in

(13)

This page was built for publication: Goodness of trees for generalized books

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1087890)