Partitioning and coloring with degree constraints

Abstract

We prove that if $G$ is a vertex critical graph with $\chi (G)\ge \Delta (G)+1-p\ge 4$ for some $p\in \mathbb{N}$ and $ω(\fancy{H}(G)) \leq \frac{χ(G) + 1}{p + 1} - 2$, then $G=K_{\chi (G)}$ or $G=O_5$. Here $\fancy{H}(G)$ is the subgraph of $G$ induced on the vertices of degree at least $\chi (G)$. This simplifies and improves the results in the paper of Kostochka, Rabern and Stiebitz \cite{krs_one}.

fixed some history

Cited by in corpus (1)

• New approach to the $k$-independence number of a graph