Decomposition of graphs and $\chi$-boundedness

Decomposition of graphs and $\chi$-boundedness

Tue, 02/03/2010
14:30 		Nicolas Trotignon (Paris) Combinatorial Theory Seminar Add to calendar L3
Decomposition of graphs and $ \chi $-boundedness
A graph is $ \chi $-bounded with a function $ f $ is for all induced subgraph H of G, we have $ \chi(H) \le f(\omega(H)) $.  Here, $ \chi(H) $ denotes the chromatic number of $ H $, and $ \omega(H) $ the size of a largest clique in $ H $. We will survey several results saying that excluding various kinds of induced subgraphs implies $ \chi $-boundedness. More precisely, let $ L $ be a set of graphs. If a $ C $ is the class of all graphs that do not any induced subgraph isomorphic to a member of $ L $, is it true that there is a function $ f $ that $ \chi $-bounds all graphs from $ C $? For some lists $ L $, the answer is yes, for others, it is no.   A decomposition theorems is a theorem saying that all graphs from a given class are either "basic" (very simple), or can be partitioned into parts with interesting relationship. We will discuss whether proving decomposition theorems is an efficient method to prove $ \chi $-boundedness.