Maximum average degree and relaxed coloring

Abstract

We say a graph is $(d,d,\dots ,d,0,\dots ,0)$-colorable with $a$ of $d$'s and $b$ of $0$'s if $V(G)$ may be partitioned into $b$ independent sets $O_1,O_2,\dots ,O_b$ and $a$ sets $D_1,D_2,\dots ,D_a$ whose induced graphs have maximum degree at most $d$. The maximum average degree, $mad(G)$, of a graph $G$ is the maximum average degree over all subgraphs of $G$. In this note, for nonnegative integers $a,b$, we show that if $mad(G)<\frac{4}{3}a+b$, then $G$ is $(1_1,1_2,\dots ,1_a,0_1,\dots ,0_b)$-colorable.

arXiv comment4 pages