On cocolourings and cochromatic numbers of graphs
type: Item
instance of: scholarly article
title: On cocolourings and cochromatic numbers of graphs
zbMATH Open document ID: 0795.05052
DOI: 10.1016/0166-218X(92)00121-2
author: Dieter Kratsch
author: John Gimbel
author: Lorna Stewart
published in: Discrete Applied Mathematics
publication date: 1994-08-29T00:00:00Z
review text: A cocolouring of a graph \(G\) is a partition of the vertices such that each set of the partition induces either a clique or an independent set in \(G\). The cochromatic number \(z(G)\) is the smallest cardinality of a cocolouring of \(G\). Given a graph \(G\) and an integer \(k\), the cochromatic number problem, i.e., determine if \(z(G) \leq k\), is known to be NP- complete. Here the authors show that it remains NP-complete for line graphs of comparability graphs and present polynomial time algorithms for computing the cochromatic number of chordal graphs and graphs containing no induced \(P_ 4\).
reviewed by: Linda Lesniak
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 68Q25
zbMATH DE Number: 513342
zbMATH Keywords: cocolouring
zbMATH Keywords: cochromatic number
zbMATH Keywords: cochromatic number problem
zbMATH Keywords: NP-complete
zbMATH Keywords: line graphs
zbMATH Keywords: comparability graphs
zbMATH Keywords: polynomial time algorithms
zbMATH Keywords: chordal graphs
MaRDI profile type: Publication
cites work: Q4724636
cites work: NP-completeness of edge-colouring some restricted graphs
cites work: Complement reducible graphs
cites work: Clustering and domination in perfect graphs
cites work: A Linear Recognition Algorithm for Cographs
cites work: Chromatic number versus chromatic number in graphs with bounded clique number
cites work: Q4198056
cites work: The intersection graphs of subtrees in trees are exactly the chordal graphs
cites work: Q4726273
cites work: Some topics in cochromatic theory
cites work: Q3328583
cites work: The NP-completeness column: an ongoing guide
cites work: Q4175304
cites work: Algorithmic Aspects of Vertex Elimination on Graphs
cites work: Cochromatic Number and the Genus of a Graph
cites work: Q4722090
cites work: Q3681937
Recommended article: On total colourings of graphs
Recommended article: Sur le coloriage des graphs
Recommended article: On the chromatic number of graphs
Recommended article: Q4722090
Recommended article: Q5716488
Recommended article: ON HYPERGRAPH COLOURINGS
Recommended article: On chromaticity of graphs
Recommended article: On coloring numbers of graph powers
Recommended article: Q4016072
Recommended article: Q4852181
description: scientific article; zbMATH DE number 513342