Is it true that for any planar graph $(V,E)$ we can divide its set of vertices $V$ into two subsets $V=V_1\sqcup V_2$ such that subgraphs with these sets of vertices (and all edges between them) are both acyclic?
Dividing planar graph into two acycliс
2
$\begingroup$
graph-theory
-
0As you probably realize, this is a strengthening of the four colorability of planar graphs, so you should expect/hope to find a counterexample. – 2011-12-10
1 Answers
0
It says here, "Conjectures: (1) Albertson-Berman [AB]: Every planar graph has an induced subgraph with at least half of the vertices that is a forest." Also, "Akiyama and Watanabe [AW] gave examples showing that Conjectures 1 and 2 are best possible." So these papers (and the rest of the discussion and links) should be relevant. Here are the bibliographic details:
[AB] Albertson, M. O.; Berman, D. M. A conjecture on planar graphs. Graph Theory and Related Topics (J. A. Bondy and U. S. R. Murty, eds.), (Academic Press, 1979), 357.
[AW] Akiyama, J.; Watanabe, M. Maximum induced forests of planar graphs. Graphs and Combinatorics 3 (1987), 201--202.
-
0Yes, there is a counterexample in [RW]. Thank you, Gerry! – 2011-12-11