perfect graph

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

\begin{problem} Let $G$ be a perfect graph on $n$ vertices. Is it true that either $G$ or $\bar{G}$ contains a complete bipartite subgraph with bipartition $(A,B)$ so that $|A|, |B| \ge n^{1 - o(1)}$? \end{problem}

Keywords: perfect graph

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

Syndicate content