On graphs \(G\) for which all large trees are \(G\)-good
type: Item
instance of: scholarly article
title: On graphs \(G\) for which all large trees are \(G\)-good
zbMATH Open document ID: 0788.05069
DOI: 10.1007/BF02988318
author: Stefan A. Burr
author: Ralph Faudree
published in: Graphs and Combinatorics
publication date: 1994-05-30T00:00:00Z
review text: 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\).
Mathematics Subject Classification ID: 05C55
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 490737
zbMATH Keywords: chromatic number
zbMATH Keywords: colors
zbMATH Keywords: surplus
zbMATH Keywords: generalized Ramsey number
zbMATH Keywords: tree
reviewed by: Gregory Loren McColm
MaRDI profile type: Publication
cites work: Ramsey Numbers Involving Graphs with Long Suspended Paths
cites work: An inequality involving the vertex arboricity and edge arboricity of a graph
cites work: Ramsey Numbers for the Pair Sparse Graph-Path or Cycle
cites work: Goodness of trees for generalized books
cites work: Q4120601
cites work: Generalized Ramsey theory for graphs. III: Small off-diagonal numbers
cites work: Multipartite graph-sparse graph Ramsey numbers
cites work: Unterteilungen vollständiger Graphen in Graphen mit unendlicher chromatischer Zahl
cites work: On Representatives of Subsets
cites work: Q5572939
cites work: Q5548826
cites work: An inequality for the chromatic number of a graph
description: scientific article; zbMATH DE number 490737