On the maximum \(q\)-colourable induced subgraph problem in perfect graphs (Q964478)
From MaRDI portal
!
This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:
scientific article; zbMATH DE number 5693411
| Language | Label | Description | Also known as |
|---|---|---|---|
| default for all languages | No label defined |
||
| English | On the maximum \(q\)-colourable induced subgraph problem in perfect graphs |
scientific article; zbMATH DE number 5693411 |
Statements
On the maximum \(q\)-colourable induced subgraph problem in perfect graphs (English)
0 references
15 April 2010
0 references
Summary: Given a non-negative integer \(q\), the maximum \(q\)-colourable induced subgraph (MCS) problem asks for an induced subgraph of maximum order among those that are \(q\)-colourable. By a result of \textit{M. Yannakakis} and \textit{F. Gavril} [``The maximum k-colorable subgraph problem for chordal graphs,'' Inf. Process. Lett. 24, 133--137 (1987; Zbl 0653.68070)] and independently of \textit{D.G. Corneil} and \textit{J. Fonlupt} [``The complexity of generalized clique covering,'' Discrete Appl. Math. 22, No.\,2, 109--118 (1989; Zbl 0685.68046)], the MCS is NP-Complete even if restricted to the class of split graphs. In this paper, we investigate the approximability of the MCS problem in the class of perfect graphs.
0 references
greedy algorithms
0 references
perfect graphs
0 references
vertex colouring
0 references
q-colourable
0 references
subgraphs
0 references
0.8432936072349548
0 references
0.8381651639938354
0 references
