Cover and variable degeneracy

Fangyao Lu, Qianqian Wang, Tao Wang

Published 2019-07-13Version 1

Let $f$ be a nonnegative integer valued function on the vertex-set of a graph. A graph is {\bf strictly $f$-degenerate} if each nonempty subgraph $\Gamma$ has a vertex $v$ such that $\deg_{\Gamma}(v) < f(v)$. In this paper, we define a new concept, strictly $f$-degenerate transversal, which generalizes list coloring, $(f_{1}, f_{2}, \dots, f_{\kappa})$-partition, signed coloring, DP-coloring and $L$-forested-coloring. A {\bf cover} of a graph $G$ is a graph $H$ with vertex set $V(H) = \bigcup_{v \in V(G)} X_{v}$, where $X_{v} = \{(v, 1), (v, 2), \dots, (v, \kappa)\}$; the edge set $\mathscr{M} = \bigcup_{uv \in E(G)}\mathscr{M}_{uv}$, where $\mathscr{M}_{uv}$ is a matching between $X_{u}$ and $X_{v}$. A vertex set $R \subseteq V(H)$ is a {\bf transversal} of $H$ if $|R \cap X_{v}| = 1$ for each $v \in V(G)$. A transversal $R$ is a {\bf strictly $f$-degenerate transversal} if $H[R]$ is strictly $f$-degenerate. The main result of this paper is a degree type result, which generalizes Brooks' theorem, Gallai's theorem, degree-choosable, signed degree-colorable, DP-degree-colorable. Similar to Borodin, Kostochka and Toft's variable degeneracy, the degree type result is also self-strengthening. Using these results, we can uniformly prove many new and known results.