2
$\begingroup$

Thomassen proved that the vertex set of every planar graph can be decomposed into two sets inducing a 1-degenerate graph and a 2-degenerate graph, respectively (C. Thomassen, Decomposing a planar graph into degenerate graphs).

I would like to know if the following related problem is known and how it can be solved:

Can the edge set $E$ and the vertex set $V$ of every planar graph $G=(V,E)$ be partitioned into two sets $E_1, E_2$ and $V_1,V_2$ such that $G_1=(V_1,E_1)$ is 1-degenerate and $G_2=(V_1 \cup V_2,E_2)$ is a 2-degenerate graph?

All graphs are considered simple (having no loops and no parallel edges), finite and undirected.

Improve this question
$\endgroup$
1
  • $\begingroup$ If true, then we may assume that $V_1=V_2=V$ without loss of generality. $\endgroup$
    – Sang-il
    Commented Jan 26, 2022 at 15:09

0

Reset to default

You must log in to answer this question.