induced subgraph

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

Author(s): Gyarfas

\begin{conjecture} There exists a fixed function $f : {\mathbb N} \rightarrow {\mathbb N}$ so that $\chi(G) \le f(\omega(G))$ for every graph $G$ with no odd hole. \end{conjecture}

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

The Erdös-Hajnal Conjecture ★★★

Author(s): Erdos; Hajnal

\begin{conjecture} For every fixed graph $H$, there exists a constant $\delta(H)$, so that every graph $G$ without an induced subgraph isomorphic to $H$ contains either a clique or an independent set of size $|V(G)|^{\delta(H)}$. \end{conjecture}

Keywords: induced subgraph

Syndicate content