Amalgams and χ-Boundedness

Irena Penev

Research output: Contribution to journalJournal articleResearchpeer-review

391 Downloads (Pure)

Abstract

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.
Original languageEnglish
JournalJournal of Graph Theory
Volume84
Issue number1
Pages (from-to)57–92
ISSN0364-9024
DOIs
Publication statusPublished - 2017

Keywords

  • Hereditary classes
  • χ-bounded classes
  • Graph decompositions
  • Amalgam
  • House

Fingerprint Dive into the research topics of 'Amalgams and χ-Boundedness'. Together they form a unique fingerprint.

Cite this