Planar graph coloring with forbidden subgraphs: Why trees and paths are dangerous

Abstrakt

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.