Structural domination and coloring of some ($P_7,C_7$)-free graphs

Abstract

We show that every connected induced subgraph of a graph $G$ is dominated by an induced connected split graph if and only if $G$ is $\mathcal{C}$-free, where $\mathcal{C}$ is a set of six graphs which includes $P_7$ and $C_7$, and each containing an induced $P_5$. A similar characterisation is shown for the class of graphs which are dominated by induced complete split graphs. Motivated by these results, we study structural descriptions of some classes of $\mathcal{C}$-free graphs. In particular, we give structural descriptions for the class of ($P_7$,$C_7$,$C_4$,gem)-free graphs and for the class of ($P_7$,$C_7$,$C_4$,diamond)-free graphs. Using these results, we show that every ($P_7$,$C_7$,$C_4$,gem)-free graph $G$ satisfies $\chi (G)\le 2\omega (G)-1$, and that every ($P_7$,$C_7$,$C_4$,diamond)-free graph $H$ satisfies $\chi (H)\le \omega (H)+1$. These two upper bounds are tight for any subgraph of the Petersen graph containing a $C_5$.