Premium
Radius two trees specify χ‐bounded classes
Author(s) -
Kierstead H. A.,
Penrice S. G.
Publication year - 1994
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/jgt.3190180203
Subject(s) - combinatorics , mathematics , bounded function , tree (set theory) , class (philosophy) , chromatic scale , radius , discrete mathematics , computer science , mathematical analysis , computer security , artificial intelligence
A class of graphs χ is said to be χ‐bounded, with χ‐binding function f , if for all G ϵ Γ, χ ( G) ≦ f (ω(G)) , where χ( G ) is the chromatic number of G and ω( G ) is the clique number of G . It has been conjectured that for every tree T , the class of graphs that do not induce T is χ‐bounded. We show that this is true in the case where T is a tree of radius two.