Search
Abstract
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 P (the problem is also known as P-coloring). We focus on the computational complexity of several problems related to greedy partitioning. In particular, we show that given a graph G and an integer k deciding if the greedy algorithm outputs P-coloring with at least k colors is NP-complete if P is a class of Kp-free graphs with 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 P is finite. We also prove coNP-completeness of deciding if for a given graph G and an integer t>=0 the difference between the largest number of colors used by the greedy algorithm and the minimum number of colors required in any 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 P-coloring algorithm.
Citations
-
2
CrossRef
-
0
Web of Science
-
5
Scopus
Cite as
Full text
- Publication version
- Accepted or Published Version
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/s10878-017-0185-2
- License
-
open in new tab
Keywords
Details
- Category:
- Articles
- Type:
- artykuł w czasopiśmie wyróżnionym w JCR
- Published in:
-
JOURNAL OF COMBINATORIAL OPTIMIZATION
no. 35,
pages 641 - 665,
ISSN: 1382-6905 - Language:
- English
- Publication year:
- 2018
- Bibliographic description:
- Borowiecki P.: Computational aspects of greedy partitioning of graphs// JOURNAL OF COMBINATORIAL OPTIMIZATION. -Vol. 35, nr. 2 (2018), s.641-665
- DOI:
- Digital Object Identifier (open in new tab) 10.1007/s10878-017-0185-2
- Verified by:
- Gdańsk University of Technology
seen 219 times