chi-bounded


Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

\begin{question} Is every proper vertex-minor closed class of graphs chi-bounded? \end{question}

Keywords: chi-bounded; circle graph; coloring; vertex minor

Graphs with a forbidden induced tree are chi-bounded ★★★

Author(s): Gyarfas

Say that a family ${\mathcal F}$ of graphs is $\chi$-\emph{bounded} if there exists a function $f: {\mathbb N} \rightarrow {\mathbb N}$ so that every $G \in {\mathcal F}$ satisfies $\chi(G) \le f (\omega(G))$.

\begin{conjecture} For every fixed tree $T$, the family of graphs with no induced subgraph isomorphic to $T$ is $\chi$-bounded. \end{conjecture}

Keywords: chi-bounded; coloring; excluded subgraph; tree

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