![](/files/happy5.png)
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.
![$ f : {\mathbb N} \rightarrow {\mathbb N} $](/files/tex/e5839c90f2b5ca6fe2f58de668c9549b3ad831bd.png)
![$ \chi(G) \le f(\omega(G)) $](/files/tex/4ecaa216fb961541a2aa91c99df9d018ca9e5597.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
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
.
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ \delta(H) $](/files/tex/f3109c2657867bfbf5df1f9d878be062ffaa82d0.png)
![$ G $](/files/tex/b8e7ad0330f925492bf468b5c379baec88cf1b3d.png)
![$ H $](/files/tex/76c7b422c8e228780f70a4f31614cfcf3f831c65.png)
![$ |V(G)|^{\delta(H)} $](/files/tex/e12fe74b562523df4457275a178e2078c43c7715.png)
Keywords: induced subgraph
![Syndicate content Syndicate content](/misc/feed.png)