Computational aspects of greedy partitioning of graphs
Piotr Borowiecki · Journal of Combinatorial Optimization · 2017
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}}$$ (the problem is also known as $${\mathcal {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}}$$ -coloring with at least k colors is $$\mathbb {NP}$$ -complete if $${\mathcal {P}}$$ is a class of $$K_p$$ -free graphs with $$p\ge 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}}$$ is finite. We also prove $$\text {co}\mathbb {NP}$$ -completeness of deciding if for a given graph G and an integer $$t\ge 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}}$$ -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}}$$ -coloring algorithm.