错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Variable Degeneracy of Planar Graphs without Chorded 6-Cycles

  • Hui Hui Fang,
  • Dan Jun Huang,
  • Tao Wang,
  • Wei Fan Wang

摘要

A cover of a graph G is a graph H with vertex set V (H) = ∪vV(G) Lv, where Lv = {v} × [s], and the edge set M = ∪uvE(G) Muv, where Muv is a matching between Lu and Lv. A vertex set TV (H) is a transversal of H if ∣TLv∣ = 1 for each vV(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 xV (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.