excluded subgraph


Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family $ {\mathcal F} $ of graphs is $ \chi $-bounded if there exists a function $ f: {\mathbb N} \rightarrow {\mathbb N} $ so that every $ G \in {\mathcal F} $ satisfies $ \chi(G) \le f (\omega(G)) $.

Conjecture   For every fixed tree $ T $, the family of graphs with no induced subgraph isomorphic to $ T $ is $ \chi $-bounded.

Keywords: chi-bounded; coloring; excluded subgraph; tree

Syndicate content