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?

  • $\begingroup$ 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). $\endgroup$ – Gordon Royle Nov 28 '15 at 15:04
  • $\begingroup$ 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. $\endgroup$ – hbm Nov 28 '15 at 16:58

I don't know the answer for your question, but I know a somewhat related problem.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.