Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|cite|improve this question
As you probably realize, this is a strengthening of the four colorability of planar graphs, so you should expect/hope to find a counterexample. – user83827 Dec 10 '11 at 22:26
up vote 0 down vote accepted

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.

share|cite|improve this answer
Yes, there is a counterexample in [RW]. Thank you, Gerry! – Alex Nelson Dec 11 '11 at 1:04

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.