Amalgams and χ-Boundedness

A class of graphs is hereditary if it is closed under isomorphism and induced subgraphs. A class G of graphs is χ-bounded if there exists a function f : N → N such that for all graphs G ∈ G, and all induced subgraphs H of G, we have that χ(H) ≤ f (ω(H)). We prove that proper homogeneous sets, clique-cutsets, and amalgams together preserve χ-boundedness. More precisely, we show that if G and G∗ are hereditary classes of graphs such that G is χ-bounded, and such that every graph in G∗ either belongs to G or admits a proper homogeneous set, a clique-cutset, or an amalgam, then the class G∗ is χ-bounded. This generalizes a result of [J Combin Theory Ser B 103(5) (2013), 567–586], which states that proper homogeneous sets and clique-cutsets together preserve χ-boundedness, as well as a result of [European J Combin 33(4) (2012), 679–683], which states that 1-joins preserve χ-boundedness. The house is the complement of the four-edge path. As an application of our result and of the decomposition theorem for “cap-free” graphs from [J Graph Theory 30(4) (1999), 289–308], we obtain that if G is a graph that does not contain any subdivision of the house as an induced subgraph, then χ(G) ≤ 3ω(G)−1.