Variable Degeneracy of Planar Graphs without Chorded 6-Cycles
摘要
A cover of a graph G is a graph H with vertex set V (H) = ∪v∈V(G) Lv, where Lv = {v} × [s], and the edge set M = ∪uv∈E(G) Muv, where Muv is a matching between Lu and Lv. A vertex set T ⊆ V (H) is a transversal of H if ∣T ∩ Lv∣ = 1 for each v ∈ V(G). Let f be a nonnegative integer valued function on the vertex-set of H. If for any nonempty subgraph Γ of H[T], there exists a vertex x ∈ V (H) such that d(x) < f(x), then T is called a strictly f-degenerate transversal. In this paper, we give a sufficient condition for the existence of strictly f-degenerate transversal for planar graphs without chorded 6-cycles. As a consequence, every planar graph without subgraphs isomorphic to the configurations is DP-4-colorable.