On the Tight Chromatic Bounds for a Class of Graphs without Three Induced Subgraphs

2016/07/28 by Dhurandhar, Medha
#05C #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1607.08312

Abstract

Here we prove that a graph without some three induced subgraphs has chromatic number at the most equal to its maximum clique size plus one. Further we show that the bounds are tight and give examples to show that each of the three forbidden subgraphs is necessary in the hypothesis.

Related

• Tight Chromatic Number for a class of Graphs with two forbidden subgraphs
• Tight Chromatic Upper Bound for 3K1, K1+C4-free Graphs
• Tight Chromatic Upper Bound for 3K1, C5-free Graphs
• Polynomial bounds for chromatic number. IV. A near-polynomial bound for excluding the five-vertex path
• Induced subgraphs of induced subgraphs of large chromatic number