Computational aspects of greedy partitioning of graphs

Piotr Borowiecki ()
Additional contact information
Piotr Borowiecki: Gdańsk University of Technology

Journal of Combinatorial Optimization, 2018, vol. 35, issue 2, No 22, 665 pages

Abstract: 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 $${\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.

Keywords: Graph partitioning; Computational complexity; Graph coloring; Greedy algorithm; Grundy number; Minimal graphs; 68Q17; 68R10; 05C85; 05C15 (search for similar items in EconPapers)
Date: 2018
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-017-0185-2 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:35:y:2018:i:2:d:10.1007_s10878-017-0185-2

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-017-0185-2

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().