Cover and variable degeneracy
share
Let f be a nonnegative integer valued function on the vertex-set of a graph. A graph is strictly f-degenerate if each nonempty subgraph Γ has a vertex v such that _Γ(v) < f(v). In this paper, we define a new concept, strictly f-degenerate transversal, which generalizes list coloring, (f_1, f_2, ..., f_κ)-partition, signed coloring, DP-coloring and L-forested-coloring. A cover of a graph G is a graph H with vertex set V(H) = _v ∈ V(G) X_v, where X_v = {(v, 1), (v, 2), ..., (v, κ)}; the edge set M = _uv ∈ E(G)M_uv, where M_uv is a matching between X_u and X_v. A vertex set R ⊆ V(H) is a transversal of H if |R ∩ X_v| = 1 for each v ∈ V(G). A transversal R is a 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.
READ FULL TEXT