# induced subgraph

## Bounding the chromatic number of graphs with no odd hole ★★★

Author(s): Gyarfas

**Conjecture**There exists a fixed function so that for every graph with no odd hole.

Keywords: chi-bounded; coloring; induced subgraph; odd hole; perfect graph

## The Erdös-Hajnal Conjecture ★★★

**Conjecture**For every fixed graph , there exists a constant , so that every graph without an induced subgraph isomorphic to contains either a clique or an independent set of size .

Keywords: induced subgraph