pith. sign in

arxiv: 1202.5855 · v2 · pith:SD73HYTJnew · submitted 2012-02-27 · 🧮 math.CO

Partitioning and coloring with degree constraints

classification 🧮 math.CO
keywords degreefancycitecoloringconstraintscriticaldeltafrac
0
0 comments X
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.