pith. machine review for the scientific record. sign in

arxiv: 1806.07021 · v1 · submitted 2018-06-19 · 🧮 math.CO

Recognition: unknown

Maximum average degree and relaxed coloring

Authors on Pith no claims yet
classification 🧮 math.CO
keywords ldotsdegreemaximumaveragecolorablegraphsetscoloring
0
0 comments X
read the original abstract

We say a graph is $(d, d, \ldots, d, 0, \ldots, 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,\ldots,O_b$ and $a$ sets $D_1, D_2,\ldots, 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, \ldots, 1_a, 0_1, \ldots, 0_b)$-colorable.

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.