Cover and variable degeneracy

Abstract

Let $f$ be a nonnegative integer valued function on the vertex set of a graph. A graph is \textbf{strictly $f$-degenerate} if each nonempty subgraph $\Gamma$ has a vertex $v$ such that ${\mathrm{deg}}_{\Gamma }(v)<f(v)$. In this paper, we define a new concept, strictly $f$-degenerate transversal, which generalizes list coloring, signed coloring, DP-coloring, $L$-forested-coloring, and $(f_1,f_2,\dots ,f_s)$-partition. A \textbf{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,s)\}$; the edge set $\mathcal{M}={\bigcup }_{uv\in E(G)}{\mathcal{M}}_{uv}$, where ${\mathcal{M}}_{uv}$ is a matching between $X_u$ and $X_v$. A vertex set $R\subseteq V(H)$ is a \textbf{transversal} of $H$ if $|R\cap X_v|=1$ for each $v\in V(G)$. A transversal $R$ is a \textbf{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 result, signed degree-colorable result, and DP-degree-colorable result. We also give some structural results on critical graphs with respect to strictly $f$-degenerate transversal. Using these results, we can uniformly prove many new and known results. In the final section, we pose some open problems.

arXiv comment18 pages, 5 figures

References in corpus (6)

• The asymptotic behavior of the correspondence chromatic number
• DP-colorings of graphs with high chromatic number
• The Johansson--Molloy Theorem for DP-Coloring
• DP-4-coloring of planar graphs with some restrictions on cycles
• Analogue of DP-coloring on variable degeneracy and its applications on list vertex-arboricity and DP-coloring
• Variable degeneracy on toroidal graphs

Cited by in corpus (4)

• Planar graphs without normally adjacent short cycles
• DP-3-coloring of planar graphs without certain cycles
• Variable degeneracy on toroidal graphs
• An extension of Thomassen's result on choosability