Goodness of trees for generalized books
type: Item
instance of: scholarly article
title: Goodness of trees for generalized books
zbMATH Open document ID: 0612.05046
DOI: 10.1007/BF01788524
author: Stefan A. Burr
author: Ralph Faudree
author: Cecil Rousseau
author: R. H. Schelp
author: Ronald Gould
author: Michael Jacobson
author: P. Erdős
published in: Graphs and Combinatorics
publication date: 1987-01-01T00:00:00Z
review text: 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.
Mathematics Subject Classification ID: 05C55
zbMATH DE Number: 3989390
zbMATH Keywords: chromatic surplus
zbMATH Keywords: coloring
zbMATH Keywords: F-good
reviewed by: Jack E. Graver
MaRDI profile type: Publication
cites work: Ramsey Numbers for the Pair Sparse Graph-Path or Cycle
cites work: Q3825106
cites work: On Ramsey numbers involving starlike multipartite graphs
cites work: Multipartite graph-sparse graph Ramsey numbers
cites work: On Representatives of Subsets
cites work: Q5572939
full work available at URL: https://doi.org/10.1007/bf01788524
OpenAlex ID: W2112129254
Wikidata QID: Q105723866
description: scientific article; zbMATH DE number 3989390