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

Partitioning planar graph of girth 5 into two forests with maximum degree 4

  • Min Chen,
  • André Raspaud,
  • Weifan Wang,
  • Weiqiang Yu

摘要

Given a graph G = (V, E), if we can partition the vertex set V into two nonempty subsets V1 and V2 which satisfy Δ(G[V1]) ⩽ d1 and Δ(G[V2]) ⩽ d2, then we say G has a ( \({{\rm{\Delta }}_{{d_1}}}\,,{{\rm{\Delta }}_{{d_2}}}\) Δ d 1 , Δ d 2 )-partition. And we say G admits an ( \({F_{d_{1}}}, {F_{d_{2}}}\) F d 1 , F d 2 )-partition if G[V1] and G[V2] are both forests whose maximum degree is at most d1 and d2, respectively. We show that every planar graph with girth at least 5 has an (F4, F4)-partition.