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?

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

1 Answer 1

Reset to default
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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .