MAXIMUM H-COLORABLE SUBGRAPH PROBLEM IN BALANCED GRAPHS

Authors
DAHLHAUS E MANUEL PD MILLER M
Citation
E. Dahlhaus et al., MAXIMUM H-COLORABLE SUBGRAPH PROBLEM IN BALANCED GRAPHS, Information processing letters, 65(6), 1998, pp. 301-303
Citations number
7
Categorie Soggetti
Computer Science Information Systems","Computer Science Information Systems
Journal title
Information processing letters → ACNP
ISSN journal
00200190
Volume
65
Issue
6
Year of publication
1998
Pages
301 - 303
Database
ISI
SICI code
0020-0190(1998)65:6<301:MHSPIB>2.0.ZU;2-A
Abstract
The k-fold clique transversal problem is to locate a minimum set Omega of vertices of a graph such that every maximal clique has at least k elements of Omega. The maximum h-colourable subgraph problem is to fin d a maximum subgraph of a graph which is h-colourable. We show that th e k-fold clique transversal problem and the maximum h-colourable subgr aph problem are polynomially solvable on balanced graphs. We also prov ide a polynomial algorithm to recognize balanced graphs. (C) 1998 Else vier Science B.V.