- This event has passed.

# Eun-Kyung Cho (조은경), Decomposition of a planar graph into a $d$-degenerate graph and a graph with maximum degree at most $h$

## Tuesday, March 3, 2020 @ 4:30 PM - 5:30 PM KST

Given a graph $G$, a *decomposition* of $G$ is a collection of spanning subgraphs $H_1, \ldots, H_t$ of $G$ such that each edge of $G$ is an edge of $H_i$ for exactly one $i \in \{1, \ldots, t\}$. Given a positive integer $d$, a graph is said to be $d$-*degenerate* if every subgraph of it has a vertex of degree at most $d$. Given a non-negative integer $h$, we say that a graph $G$ is $(d,h)$-*decomposable* if there is a decomposition of $G$ into two spanning subgraphs, where one is a $d$-degenerate graph, and the other is a graph with maximum degree at most $h$.

It is known that a planar graph is $5$-degenerate, but not always $4$-degenerate. This implies that a planar graph is $(5,0)$-decomposable, but not always $(4,0)$-decomposable. Moreover, by related previous results, it is known that a planar graph is $(3,4)$- and $(2,8)$-decomposable.

In this talk, we improve these results by showing that every planar graph is $(4,1)$-, $(3,2)$-, and $(2,6)$-decomposable. The $(4,1)$- and $(3,2)$-decomposabilities are sharp in the sense that the maximum degree condition cannot be reduced more.

This is joint work with Ilkyoo Choi, Ringi Kim, Boram Park, Tingting Shan, and Xuding Zhu.