科研之友
微信
新浪微博
Facebook
分享链接
摘要
Let G be a graph. For two positive integers d and h, a (d, h)-decomposition of G is a pair (G, H) such that H is a subgraph of G of maximum degree at most h and D is an acyclic orientation of G-E(H) of maximum out-degree at most d. A graph G is (d, h)-decomposable if G has a (d, h)-decomposition. In this paper, we prove that every planar graph without intersecting 3-cycles and adjacent 4(-)-cycles is (2, 1)-decomposable. As a corollary, we obtain that every planar graph without intersecting 3-cycles and adjacent 4(-)-cycles has a matching M such that G-M is 2-degenerate and hence G-M is DP-3-colorable and Alon-Tarsi number of G-M is at most 3.
