Complexity of fall coloring for restricted graph classes

Juho Lauri, Christodoulos Mitillos

We strengthen a result by Laskar and Lyle (Discrete Appl. Math. (2009), 330-338) by proving that it is NP-complete to decide whether a bipartite planar graph can be partitioned int…