Premium
On the Loebl–Komlós–Sós conjecture
Author(s) -
Bazgan Cristina,
Li Hao,
Woźniak Mariusz
Publication year - 2000
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/1097-0118(200008)34:4<269::aid-jgt3>3.0.co;2-y
Subject(s) - conjecture , combinatorics , mathematics , graph , discrete mathematics
The Loebl–Komlós–Sós conjecture says that any graph G on n vertices with at least half of vertices of degree at least k contains each tree of size k . We prove that the conjecture is true for paths as well as for large values of k ( k ≥ n − 3). © 2000 John Wiley & Sons, Inc. J Graph Theory 34: 269–276, 2000