Date : Feb. 26, 2015, 3:30 p.m. - Room :Salle A213
Amalgams and chi-boundedness.
Mme. Irena PENEV - LIP MC2 - Ens de Lyon
Pas de possibilité de visio-conférence A class of graphs is _hereditary_ if it is closed under isomorphism and induced subgraphs. A hereditary class GG is _chi-bounded_ if there exists a non-decreasing function f:N—>N (called a _chi-bounding function_ for GG) such that every graph G in GG satisfies chi(G) <= f(omega(G)), where chi(G) is the chromatic number of G, and omega(G) is the clique number (i.e. the maximum size of a clique) of G. For many hereditary classes of graphs, there is a decomposition theorem of the following form : every graph in the class either belongs to some class of well-understood basic graphs, or it admits one of several decompositions. This raises the following question : which graph decompositions preserve chi-boundedness ? Formally, we say that a graph decomposition D _preserves chi-boundedness_ if for all hereditary classes GG and GG* such that GG is chi-bounded and every graph in GG* either belongs to GG or admits the decomposition D, we have that GG* is chi-bounded (however, the optimal chi-bounding functions for GG and GG* need not be the same). This can be generalized to several decompositions : we say that graph decompositions D1,...,Dk _together preserve chi-boundedness_ if for all hereditary classes GG and GG* such that GG is chi-bounded and every graph in GG* either belongs to GG or admits at least one of D1,...,Dk, we have that GG* is chi-bounded. The fact that each of D1,...,Dk individually preserves chi-boundedness does not imply that D1,...,Dk together preserve it (this essentially follows from the fact that the preservation of chi-boundedness does not entail the preservation of the optimal chi-bounding function). Our main result is that proper homogeneous sets, clique-cutsets, and amalgams together preserve chi-boundedness. This generalizes two earlier results : that proper homogeneous sets and clique-cutsets together preserve chi-boundedness (due to Chudnovsky, Penev, Scott, and Trotignon ), and that 1-joins preserve chi-boundedness (due to Dvorak and Kral ). As an application of this result, as well as of a decomposition theorem for 'cap-free' graphs (due to Conforti, Cornuejols, Kapoor, and Vuskovic ), we show that the class of graphs that do not contain any subdivision of the 'house' (i.e. the complement of the four-edge path) as an induced subgraph is chi-bounded. References  M. Chudnovsky, I. Penev, A.D. Scott, and N. Trotignon. Substitution and chi-boundedness. J. Combin. Theory Ser. B, 103(5):567-586, 2013.  M. Conforti, G. Cornuejols, A. Kapoor, and K. Vuskovic. Even and odd holes in cap-free graphs. J. Graph Theory, 30(4):289-308, 1999.  Z. Dvorak and D. Kral. Classes of graphs with small rank decompositions are chi-bounded. European J. Combin., 33(4):679-683, 2012.