Anzeige
Erschienen in:
2017 | OriginalPaper | Buchkapitel
On Computational Aspects of Greedy Partitioning of Graphs
verfasst von : Piotr Borowiecki
Erschienen in: Frontiers in Algorithmics
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
In this paper we consider a problem of graph \({\mathcal P}\)-coloring consisting in partitioning the vertex set of a graph such that each of the resulting sets induces a graph in a given additive, hereditary class of graphs \({\mathcal P}\). We focus on partitions generated by the greedy algorithm. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs a \({\mathcal P}\)-coloring with a least k colors is \(\mathbb {NP}\)-complete for an infinite number of classes \({\mathcal P}\). On the other hand we get a polynomial-time certifying algorithm if k is fixed and the family of minimal forbidden graphs defining the class \({\mathcal P}\) is finite. We also prove \(\mathrm{co}\mathbb {NP}\)-completeness of the problem of deciding whether for a given graph G 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 a given constant. A new Brooks-type bound on the largest number of colors used by the greedy \({\mathcal P}\)-coloring algorithm is given.