Date
Tue, 02 Mar 2010
Time
14:30 - 15:30
Location
L3
Speaker
Nicolas Trotignon
Organisation
Paris

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. 

Please contact us with feedback and comments about this page. Last updated on 03 Apr 2022 01:32.