Vertex partitions of (C_3,C_4,C_6)-free planar graphs
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.
READ FULL TEXT