Open Problem Garden

Author(s): Gyarfas

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.

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

Posted by mdevos
updated June 25th, 2007

add new comment

Open Problem Garden

Fox, Jacob

Jungic, Veselin

Mahdian, Mohammad

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

Gyarfas, Andras

perfect graph

odd hole

Cusick, Thomas W.

Wills, Jorg M.

diophantine approximation

Navigate

Recent Activity