Independent sets of maximum weight in (\(p,q\))-colorable graphs.
type: Item
instance of: scholarly article
title: Independent sets of maximum weight in (\(p,q\))-colorable graphs.
zbMATH Open document ID: 1034.05020
DOI: 10.1016/S0012-365X(02)00877-4
author: Vadim Lozin
author: V. E. Alekseev
published in: Discrete Mathematics
publication date: 2003-05-25T00:00:00Z
review text: The authors consider \((p,q)\)-colorable graphs (their vertex sets can be partitioned into at most \(p\) cliques and \(q\) independent sets). In particular, \((0,2)\)-colorable graphs are bipartite, and \((1,1)\)-colorable are split graphs. For both of these classes, the problem of finding a maximum weight independent set is known to be solvable in polynomial time. In this note the authors give a complete classification of the family of \((p,q)\)-colorable graphs with respect to time complexity of this problem. Specifically, they show that the problem has a polynomial time solution in the class of \((p,q)\)-colorable graphs if and only if \(q \leq 2\) (assuming \(\mathcal{P} \neq \mathcal{NP}\)).
reviewed by: Ingo Schiermeyer
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1915552
zbMATH Keywords: weighted graph
zbMATH Keywords: independent set
zbMATH Keywords: polynomial algorithm
MaRDI profile type: Publication
cites work: On graphs with polynomially solvable maximum-weight clique problem
cites work: A nice class for the vertex packing problem
cites work: Q5782525
cites work: The complexity of generalized clique packing
cites work: Q4193514
cites work: Q3903002
cites work: Q3216686
cites work: Matching theory
cites work: On maximal independent sets of vertices in claw-free graphs
cites work: A REVISION OF MINTY'S ALGORITHM FOR FINDING A MAXIMUM WEIGHT STABLE SET OF A CLAW-FREE GRAPH
cites work: Q4770411
cites work: Q4871056
cites work: Algorithme de recherche d'un stable de cardinalité maximum dans un graphe sans étoilé
cites work: A New Algorithm for Generating All the Maximal Independent Sets
full work available at URL: s0012-365x(02)00877-4
OpenAlex ID: W2096226903
description: scientific article; zbMATH DE number 1915552