Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8901139 | Applied Mathematics and Computation | 2018 | 7 Pages |
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
Min Chen, Weiqiang Yu, Weifan Wang,