Bounding chromatic number for graphs in Forb*(bull)

Thursday, September 30, 2010 -
2:30pm to 4:30pm
Given a graph $H, Forb(H)$ is the class of all graphs that do not contain $H$ as an induced subgraph, and $Forb^*(H)$ is the class of all graphs that do not contain any subdivision of $H$ as an induced subgraph. A class $\Gamma$ of graphs is $\chi$-bound if there exists a function $f : N \rightarrow N$ (called a $\chi$-binding function for $\Gamma$) such that for all $G \in \Gamma, \chi(G) \leq f(\omega(G))$.  $\chi$-bound classes of graphs were introduced in 1987 by András Gyárfás as a generalization of the class of perfect graphs. Gyárfás conjectured that for any tree $T$, the class $Forb(T)$ is $\chi$-bound. In 1997, Alex Scott proved a 'topological' version of this conjecture: for any tree $T$, the class $Forb^*(T)$ is $\chi$-bound; he then conjectured that for every graph $H$, the class $Forb^*(H)$ is $\chi$-bound.The bull is the graph consisting of a triangle and two disjoint pendant edges, and an (m,n)-bull is the graph obtained from the bull by subdividing one pendant edge $m-1$ times and the other $n-1$ times. In this talk, we present proofs of two special classes of Scott's conjecture: we first outline a proof of the fact that the class $Forb^*(bull)$ is $\chi$-bound by a quadratic function, and then we discuss a proof that the for all m and n, the class $Forb^*((m,n)-bull)$ is $\chi$-bound by an exponential function.Joint work with Maria Chudnovsky, Alex Scott, and Nicolas Trotignon.
Irena Penev
Columbia University
Event Location: 
Fine Hall 224