Approximating minimum cocolorings.
type: Item
instance of: scholarly article
title: Approximating minimum cocolorings.
zbMATH Open document ID: 1042.68091
DOI: 10.1016/S0020-0190(02)00288-0
author: Fedor V. Fomin
author: Dieter Kratsch
author: Jean-Christophe Novelli
published in: Information Processing Letters
publication date: 2003-01-21T00:00:00Z
review text: A cocoloring of a graph \(G\) is a partition of the vertex set of \(G\) such that each set of the partition is either a clique or an independent set in \(G.\) Some special cases of the minimum cocoloring problem are of particular interest. We provide polynomial-time algorithms to approximate a minimum cocoloring on graphs, partially ordered sets and sequences. In particular, we obtain an efficient algorithm to approximate within a factor of \(1.71\) a minimum partition of a partially ordered set into chains and antichains, and a minimum partition of a sequence into increasing and decreasing subsequences.
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68W05
zbMATH DE Number: 1856489
zbMATH Keywords: Approximation algorithms
zbMATH Keywords: Graphs
zbMATH Keywords: Partially ordered sets
zbMATH Keywords: Sequences
Wikidata QID: Q56428494
MaRDI profile type: Publication
cites work: Subgraphs with a large cochromatic number
cites work: Q4724636
cites work: Graph Classes: A Survey
cites work: Critically cochromatic graphs
cites work: Q3139768
cites work: Some extremal results in cochromatic and dichromatic theory
cites work: Chromatic number versus chromatic number in graphs with bounded clique number
cites work: On chain and antichain families of a partially ordered set
cites work: On cocolourings and cochromatic numbers of graphs
cites work: Some topics in cochromatic theory
cites work: Q3328583
cites work: Some partitions associated with a partially ordered set
cites work: The structure of Sperner k-families
cites work: Geometric algorithms and combinatorial optimization
cites work: Approximation algorithms for combinatorial problems
cites work: Q4175304
cites work: On the ratio of optimal integral and fractional covers
cites work: Note on the cochromatic number of several surfaces
cites work: Q3681937
full work available at URL: s0020-0190(02)00288-0
OpenAlex ID: W1984312288
DBLP publication ID: journals/ipl/FominKN02
description: scientific article; zbMATH DE number 1856489