Vertex partitions of (C_3,C_4,C_6)-free planar graphs

11/23/2017

∙

by   Francois Dross, et al.

∙

0

∙

share

A graph is (k_1,k_2)-colorable if its vertex set can be partitioned into a graph with maximum degree at most k_1 and and a graph with maximum degree at most k_2. We show that every (C_3,C_4,C_6)-free planar graph is (0,6)-colorable. We also show that deciding whether a (C_3,C_4,C_6)-free planar graph is (0,3)-colorable is NP-complete.