Equitable partition of planar graphs

被引：4

作者：

Kim, Ringi ^{[1
]}

Oum, Sang-il ^{[2
,3
]}

Zhang, Xin ^{[4
]}

机构：

[1] Inha Univ, Dept Math, Incheon, South Korea

[2] Inst Basic Sci IBS, Discrete Math Grp, Daejeon, South Korea

[3] Korea Adv Inst Sci & Technol, Dept Math Sci, Daejeon, South Korea

[4] Xidian Univ, Sch Math & Stat, Xian 710071, Peoples R China

来源：

DISCRETE MATHEMATICS | 2021年 / 344卷 / 06期

基金：

中国国家自然科学基金; 新加坡国家研究基金会;

关键词：

Induced forest; Degenerate graph; Equitable partition; Planar graph;

D O I：

10.1016/j.disc.2021.112351

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

An equitable k-partition of a graph G is a collection of induced subgraphs (G[V-1], G[V-2], ... , G[V-k]) of G such that (V-1, V-2, ... , V-k) is a partition of V(G) and -1 <= |V-i| - |V-j| <= 1 for all 1 <= i < j <= k. We prove that every planar graph admits an equitable 2-partition into 3-degenerate graphs, an equitable 3-partition into 2-degenerate graphs, and an equitable 3-partition into two forests and one graph. (c) 2021 Elsevier B.V. All rights reserved.

引用

页数：6

共 20 条

[1] Acyclic 4-Choosability of Planar Graphs with No 4- and 5-Cycles [J].