Home » Keyword index

chi-bounded


Graph Theory » Coloring » Vertex coloring

Are vertex minor closed classes chi-bounded? ★★

Author(s): Geelen

Question   Is every proper vertex-minor closed class of graphs chi-bounded?

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

Posted by mdevos
updated May 16th, 2009
add new comment
Graph Theory » Coloring » Vertex coloring

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

Author(s): Gyarfas

Say that a family $ {\mathcal F} $ of graphs is $ \chi $-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)) $.

Conjecture   For every fixed tree $ T $, the family of graphs with no induced subgraph isomorphic to $ T $ is $ \chi $-bounded.

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

Posted by mdevos
updated May 16th, 2009
add new comment
Graph Theory » Coloring » Vertex coloring

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

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
Syndicate content