Article ID Journal Published Year Pages File Type
8901139 Applied Mathematics and Computation 2018 7 Pages PDF
Abstract
The maximum average degree of G is defined to be mad(G)=max{2|E(H)||V(H)|:H⊆G}. Borodin and Kostochka (2014) proved that every graph G with mad(G)≤83 admits an (I, Δ2)-partition and every graph G with mad(G)≤145 admits an (I, Δ4)-partition. In this paper, we obtain a strengthening result by showing that for any k ≥ 2, every graph G with mad(G)≤2+kk+1 admits an (I, Fk)-partition. As a corollary, every planar graph with girth at least 7 admits an (I, F4)-partition and every planar graph with girth at least 8 admits an (I, F2)-partition. The later result is best possible since neither girth condition nor the class of F2 can be further improved.
Related Topics
Physical Sciences and Engineering Mathematics Applied Mathematics
Authors
, , ,