Decomposing planar graphs into graphs with degree restrictions - Cho, Eun Kyung; Choi, Ilkyoo; Kim, Ringi; Park, Boram; Shan, Tingting; Zhu, Xuding (Journal of Graph Theory, 2022)
Given a graph (Formula presented.), a decomposition of (Formula presented.) is a partition of its edges. A graph is (Formula presented.) -decomposable if its edge set can be partitioned into a (Formula presented.) -degenerate graph and a graph with maximum degree at most (Formula presented.). For (Formula presented.), we are interested in the minimum integer (Formula presented.) such that every planar graph is (Formula presented.) -decomposable. It was known that (Formula presented.), (Formula presented.), and (Formula presented.). This paper proves that (Formula presented.), and (Formula presented.).
Keywords: Degenerate graphs; Degree restrictions; Edge-sets; Graph decompositions; Maximum degree; Planar graph; graph decomposition; planar graph