Variable degeneracy on toroidal graphs
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). A cover of a graph G is a graph H with vertex set V(H) = _v ∈ V(G) L_v, where L_v = { (v, 1), (v, 2), ..., (v, κ) }; the edge set M = _uv ∈ E(G)M_uv, where M_uv is a matching between L_u and L_v. A vertex set R ⊆ V(H) is a transversal of H if |R ∩ L_v| = 1 for each v ∈ V(G). A transversal R is a strictly f-degenerate transversal if H[R] is strictly f-degenerate. In this paper, we give some structural results on planar and toroidal graphs with forbidden configurations, and give some sufficient conditions for the existence of strictly f-degenerate transversal by using these structural results.
READ FULL TEXT