Séminaire

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 [1]), and that 1-joins preserve chi-boundedness (due to Dvorak and Kral [3]). As an application of this result, as well as of a decomposition theorem for 'cap-free' graphs (due to Conforti, Cornuejols, Kapoor, and Vuskovic [2]), 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 [1] M. Chudnovsky, I. Penev, A.D. Scott, and N. Trotignon. Substitution and chi-boundedness. J. Combin. Theory Ser. B, 103(5):567-586, 2013. [2] 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. [3] Z. Dvorak and D. Kral. Classes of graphs with small rank decompositions are chi-bounded. European J. Combin., 33(4):679-683, 2012.