An optimal χ‐bound for (P6, diamond)‐free graphs
Kathie Cameron, Shenwei Huang, Owen Merkel
Abstract
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.
Topics & Concepts
CombinatoricsMathematicsPerfect graphDiscrete mathematicsChromatic scaleGraphClique numberCographVertex (graph theory)Line graphPathwidthAdvanced Graph Theory ResearchLimits and Structures in Graph TheoryGraph Labeling and Dimension Problems