Premium
Induced trees in graphs of large chromatic number
Author(s) -
Scott A. D.
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(199704)24:4<297::aid-jgt2>3.0.co;2-j
Subject(s) - combinatorics , mathematics , integer (computer science) , conjecture , subdivision , graph , tree (set theory) , discrete mathematics , chromatic scale , computer science , archaeology , history , programming language
Gyárfás and Sumner independently conjectured that for every tree T and integer k there is an integer f(k, T) such that every graph G with χ(G) > f(k, t) contains either K k or an induced copy of T . We prove a ‘topological’ version of the conjecture: for every tree T and integer k there is g(k,T) such that every graph G with χ(G) > g(k,t) contains either K k or an induced copy of a subdivision of T . © 1997 John Wiley & Sons, Inc.