Partitioning and coloring with degree constraints

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

No reviews yet.

No comments yet.