Computational aspects of greedy partitioning of graphs

In this paper we consider a variant of graph partitioning consisting in partitioning the vertex set of a graph into the minimum number of sets such that each of them induces a graph in hereditary class of graphs $${\mathcal {P}}$$ P (the problem is also known as $${\mathcal {P}}$$ P -coloring). We focus on the computational complexity of several problems related too greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs $${\mathcal {P}}$$ P -coloring with at least k colors is $$\mathbb {NP}$$ NP -complete if $${\mathcal {P}}$$ P is a class of $$K_p$$ K p -free graphs with $$p\ge 3$$ p ≥ 3 . On the other hand we give a polynomial-time algorithm when k is fixed and the family of minimal forbidden graphs defining the class $${\mathcal {P}}$$ P is finite. We also prove $$\text {co}\mathbb {NP}$$ co NP -completeness of deciding if for a given graph G and an integer $$t\ge 0$$ t ≥ 0 the difference between the largest number of colors used by the greedy algorithm and the minimum number of colors required in any $${\mathcal {P}}$$ P -coloring of G is bounded by t. In view of computational hardness, we present new Brooks-type bound on the largest number of colors used by the greedy $${\mathcal {P}}$$ P -coloring algorithm.