Take the 2-minute tour ×
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.

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|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
add comment

1 Answer

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|improve this answer
    
Yes, there is a counterexample in [RW]. Thank you, Gerry! –  Alex Nelson Dec 11 '11 at 1:04
add comment

Your Answer

 
discard

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.