Back to Search Start Over

A large tree is tKm-good.

Authors :
Luo, Zhidan
Peng, Yuejian
Source :
Discrete Mathematics. Aug2023, Vol. 346 Issue 8, pN.PAG-N.PAG. 1p.
Publication Year :
2023

Abstract

Given two graphs G and H , the Ramsey number r (G , H) is the minimum integer N such that any red-blue coloring of the edges of K N contains either a red copy of G or a blue copy of H. Let v (G) denote the number of vertices of G , and χ (G) denote the chromatic number of G. Let s (G) denote the chromatic surplus of G , the cardinality of a minimum color class taken over all proper colorings of G with χ (G) colors. Burr [3] showed that for a connected graph G and a graph H with v (G) ≥ s (H) , r (G , H) ≥ (v (G) − 1) (χ (H) − 1) + s (H). A connected graph G is called H -good if r (G , H) = (v (G) − 1) (χ (H) − 1) + s (H). Chvátal [7] showed that any tree is K m -good for m ≥ 2 , where K m denotes a complete graph with m vertices. Let t K m denote t vertex disjoint copies of K m. Recently, Hu and Peng [13] proved that any tree T n is 2 K m -good for n ≥ 3 and m ≥ 2 , they [14] also showed that any large tree is t K 2 -good for t ≥ 3. In this paper, we show that any large tree is t K m -good for t ≥ 3 and m ≥ 3. [ABSTRACT FROM AUTHOR]

Details

Language :
English
ISSN :
0012365X
Volume :
346
Issue :
8
Database :
Academic Search Index
Journal :
Discrete Mathematics
Publication Type :
Academic Journal
Accession number :
163931682
Full Text :
https://doi.org/10.1016/j.disc.2023.113502