Premium
Special monochromatic trees in two‐colored complete graphs
Author(s) -
Chen Guantao,
Schelp Richard H.,
Šoltés Ľubomír
Publication year - 1997
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/(sici)1097-0118(199701)24:1<59::aid-jgt7>3.0.co;2-i
Subject(s) - combinatorics , mathematics , vertex (graph theory) , monochromatic color , graph , wheel graph , neighbourhood (mathematics) , discrete mathematics , graph power , line graph , physics , optics , mathematical analysis
For a positive integer k , a set of k + 1 vertices in a graph is a k ‐cluster if the difference between degrees of any two of its vertices is at most k − 1. Given any tree T with at least k 3 edges, we show that for each graph G of sufficiently large order, either G or its complement contains a copy of T such that some vertices in the copy form a k ‐cluster in G . The same conclusion holds for any tree T having a vertex of degree more than k . © 1997 John Wiley & Sons, Inc.