Consider a planar graph $G$ which is a triangulation.

Is it possible to find a two-colorable subgraph $H$ of $G$ which has a common edge with every face of $G$?

It is known that it is not always possible to take $H$ to be a spanning tree. See this MO question.

Note that we do not require $H$ to be connected.

If it is true, is there an efficient algorithm to find such a subgraph?

  • 1
    $\begingroup$ Just by curiosity: may you give an example of a triangulation without such a spanning tree? $\endgroup$ – Wolfgang Apr 29 '16 at 10:23

Yes, such a subgraph always exist. Let $G$ be a planar triangulation. By the $4$-colour theorem, $G$ has a $4$-colouring. We let $H$ be the subgraph consisting of all edges with endpoints coloured $1$ and $2$, or with endpoints coloured $3$ and $4$. Since every face of $G$ is a triangle, every face must contain a $12$ edge or a $34$ edge, as required. Also, $H$ is clearly bipartite since $(X,Y)$ is a bipartition of $H$ where $X$ is the set of vertices coloured $1$ or $3$ and $Y$ is the set of vertices coloured $2$ or $4$.

Regarding the algorithmic question, there is a quadratic algorithm to find such a subgraph. This follows from this paper of Robertson, Sanders, Seymour, and Thomas, where they present a quadratic algorithm to $4$-colour planar graphs.

| cite | improve this answer | |
  • 1
    $\begingroup$ What a nice application of the 4-colour theorem! $\endgroup$ – Wolfgang Apr 29 '16 at 11:38

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.