Partitioning and coloring with degree constraints
classification
🧮 math.CO
keywords
degreefancycitecoloringconstraintscriticaldeltafrac
read the original abstract
We prove that if $G$ is a vertex critical graph with $\chi(G) \geq \Delta(G) + 1 - p \geq 4$ for some $p \in \mathbb{N}$ and $\omega(\fancy{H}(G)) \leq \frac{\chi(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}.
This paper has not been read by Pith yet.
discussion (0)
Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.