Home » Keyword index

perfect graph


Graph Theory » Basic G.T.

Complete bipartite subgraphs of perfect graphs ★★

Author(s): Fox

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)} $?

Keywords: perfect graph

Posted by mdevos
updated January 19th, 2021
1 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