Autor:	Cho, Eun-Kyung, Choi, Ilkyoo, Kim, Ringi, Park, Boram, Shan, Tingting, Zhu, Xuding
Rok vydání:	2020
Předmět:	Mathematics - Combinatorics
Druh dokumentu:	Working Paper
Popis:	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$. Comment: 16 pages, 5 figures
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2007.01517 Zobrazit plný text záznamu View this record from Arxiv