Homogeneous sets, clique-separators, critical graphs, and optimal $\chi$-binding functions

Abstract

Given a set $\mathcal{H}$ of graphs, let $f_{\mathcal{H}}^{\star }:{\mathbb{N}}_{>0}\to {\mathbb{N}}_{>0}$ be the optimal $\chi$-binding function of the class of $\mathcal{H}$-free graphs, that is, $$f_{\mathcal{H}}^{\star }(\omega )=\max \{\chi (G):G\text{ is }\mathcal{H}\text{-free, }\omega (G)=\omega \}.$$ In this paper, we combine the two decomposition methods by homogeneous sets and clique-separators in order to determine optimal $\chi$-binding functions for subclasses of $P_5$-free graphs and of $(C_5,C_7,\dots )$-free graphs. In particular, we prove the following for each $\omega \ge 1$: (i) $f_{\{P_5,banner\}}^{\star }(\omega )=f_{3K_1}^{\star }(\omega )\in \Theta ({\omega }^2/\log (\omega )),$ (ii) $f_{\{P_5,co-banner\}}^{\star }(\omega )=f_{\{2K_2\}}^{\star }(\omega )\in \mathcal{O}({\omega }^2),$ (iii) $f_{\{C_5,C_7,\dots ,banner\}}^{\star }(\omega )=f_{\{C_5,3K_1\}}^{\star }(\omega )\notin \mathcal{O}(\omega ),$ and (iv) $f_{\{P_5,C_4\}}^{\star }(\omega )=\lceil (5\omega -1)/4\rceil .$ We also characterise, for each of our considered graph classes, all graphs $G$ with $\chi (G)>\chi (G-u)$ for each $u\in V(G)$. From these structural results, we can prove Reed's conjecture -- relating chromatic number, clique number, and maximum degree of a graph -- for $(P_5,banner)$-free graphs.

References in corpus (1)

• On graphs with no induced five-vertex path or paraglider