7
$\begingroup$

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?

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

1 Answer 1

15
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ What a nice application of the 4-colour theorem! $\endgroup$
    – Wolfgang
    Apr 29, 2016 at 11:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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