An optimal χ‐bound for (P6, diamond)‐free graphs
Kathie Cameron, Shenwei Huang, Owen Merkel · Journal of Graph Theory · 2021
Abstract In this paper we show that every (, diamond)‐free graph satisfies , where and are the chromatic number and clique number of , respectively. Our bound is attained by the complement of the famous 27‐vertex Schläfli graph. Our result unifies previously known results on the existence of linear ‐binding functions for several graph classes. Our proof is based on a reduction via the Strong Perfect Graph Theorem to imperfect (, diamond)‐free graphs, a careful analysis of the structure of those graphs, and a computer search that relies on a well‐known characterization of 3‐colourable ‐free graphs.