Back to Search
Start Over
A large tree is tKm-good.
- 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]
- Subjects :
- *RAMSEY numbers
*GRAPH connectivity
*COMPLETE graphs
*TREES
Subjects
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