Goodness of trees for generalized books (Q1087890)

From MaRDI portal
scientific article
Language Label Description Also known as
English
Goodness of trees for generalized books
scientific article

    Statements

    Goodness of trees for generalized books (English)
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    0 references
    1987
    0 references
    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.
    0 references
    chromatic surplus
    0 references
    coloring
    0 references
    F-good
    0 references

    Identifiers