Skip to main content
2 of 4
top-level tag
Ben Barber
  • 4.6k
  • 2
  • 25
  • 38

Choosing two-colorable subgraph in a triangulation

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?