# Partitioning the vertex set of a planar bipartite graph into a tree and an independent set

Let $G = (V, E)$ be a planar bipartite graph such that there is a partition $(V1, V2)$ of $V$ where $V1$ induces a tree and $V2$ induces an independent set.

Is there a characterization of such graphs in the literature?

• What sort of characterisation were you hoping for? If we start with a tree, and colour it in two colours, then there would be many many ways to start adding vertices, connecting them to the tree in a planar way and keeping the 2-colouring. I can't see enough structure there to say anything useful (but I could be wrong of course). – Gordon Royle Nov 28 '15 at 15:04
• I am interested in what kind of conditions on a 2-connected planar bipartite graph would force a partition of the sort mentioned. Also of interest is the complexity question: given such a graph how difficult is it to decide if it has such a partition. – hbm Nov 28 '15 at 16:58

In this paper it is shown that, given a planar bipartite cubic graph $G$ and a set $W$ of vertices, it is NP-complete to decide if there is an induced tree containing the vertices in $W$. In this case, there is no restriction on the vertices outside the tree, and it can be the case where the structure you are looking for, being an independent set, helps.