Back to Search Start Over

Decomposing planar graphs into graphs with degree restrictions

Authors :
Cho, Eun-Kyung
Choi, Ilkyoo
Kim, Ringi
Park, Boram
Shan, Tingting
Zhu, Xuding
Publication Year :
2020

Abstract

Given a graph $G$, a decomposition of $G$ is a partition of its edges. A graph is $(d, h)$-decomposable if its edge set can be partitioned into a $d$-degenerate graph and a graph with maximum degree at most $h$. For $d \le 4$, we are interested in the minimum integer $h_d$ such that every planar graph is $(d,h_d)$-decomposable. It was known that $h_3 \le 4$, $h_2\le 8$, and $h_1 = \infty$. This paper proves that $h_4=1, h_3=2$, and $4 \le h_2 \le 6$.<br />Comment: 16 pages, 5 figures

Subjects

Subjects :
Mathematics - Combinatorics

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2007.01517
Document Type :
Working Paper