Subscribe to the weekly news from TrueShelf

0

Partitioning planar graphs

Let \(G=(V,E)\) simple planar graph. Prove that \(V\) can be partitioned into three disjoint sets \(V = V_1 \cup V_2 \cup V_3\), such that the induced subgraphs on \(V_1\), \(V_2\) and \(V_3\) are acyclic.

Related Content