Abstract
A complete characterization of the computational complexity of deciding bicolorability of planar graphs to avoid monochromatic copy a forbidden parameter graph F is proven. The problem is NP-complete when F is a tree on at least 3 vertices.
A complete characterization of the computational complexity of deciding bicolorability of planar graphs to avoid monochromatic copy a forbidden parameter graph F is proven. The problem is NP-complete when F is a tree on at least 3 vertices.