Return to Question

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?

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?

Consider a planar graph which is a triangulation.

Is it possible to find a two-colorable subgraph which has common edge with every face of our graph?

It is known that such spanning tree not always exist. Subgraph which we are looking for can be forest or it can contain some cycles that should be in separate parts.

If it is true is there known any algorithm to find such a subgraph?

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?