On the perfect $k$-divisibility of graphs

Abstract

A graph $G$ is perfectly divisible if, for every induced subgraph $H$ of $G$, either $V(H)$ is a stable set or admits a partition into two sets $X_1$ and $X_2$ such that $\omega (H[X_1])<\omega (H)$ and $H[X_2]$ is a perfect graph. In this article, we propose the following generalisation of perfectly divisible graphs. A graph $G$ is perfectly $1$-divisible if $G$ is perfect and perfectly $k$-divisible if, for every induced subgraph $H$ of $G$, either $V(H)$ is a stable set or admits a partition into two sets $X_1$ and $X_2$ such that $\omega (H[X_1])<\omega (H)$ and $H[X_2]$ is perfectly $(k-1)$-divisible, $k\in {\mathbb{N}}_{>1}$. Our main result establishes that every perfectly $k$-divisible graph $G$ satisfies $\chi (G)\le \left(\genfrac{}{}{0ex}{}{\omega (G)+k-1}{k}\right)$ which generalises the known bound for perfectly divisible graphs.

4 pages