Amalgams and χ-Boundedness

Publication: Research - peer-reviewJournal article – Annual report year: 2016

Documents

DOI

View graph of relations

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
StatePublished - 2017
CitationsWeb of Science® Times Cited: 0

    Keywords

  • Hereditary classes, χ-bounded classes, Graph decompositions, Amalgam, House
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

Download statistics

No data available

ID: 121203956