The weighted coloring problem for two graph classes characterized by small forbidden induced structures
type: Item
instance of: scholarly article
title: The weighted coloring problem for two graph classes characterized by small forbidden induced structures
zbMATH Open document ID: 1394.05034
author: D. S. Malyshev
published in: Discrete Applied Mathematics
publication date: 2018-09-06T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C85
Mathematics Subject Classification ID: 05C75
Mathematics Subject Classification ID: 68Q17
zbMATH DE Number: 6933535
zbMATH Keywords: computational complexity
zbMATH Keywords: coloring problem
zbMATH Keywords: hereditary class
zbMATH Keywords: polynomial-time algorithm
MaRDI profile type: Publication
full work available at URL: j.dam.2018.04.006
OpenAlex ID: W2802392665
cites work: The strong perfect graph theorem
cites work: Colouring diamond-free graphs
cites work: Colouring of graphs with Ramsey-type forbidden subgraphs
cites work: Colouring vertices of triangle-free graphs without forests
cites work: A Survey on the Computational Complexity of Coloring Graphs with Forbidden Subgraphs
cites work: Coloring graphs characterized by a forbidden subgraph
cites work: Q3216686
cites work: Polynomial-time algorithms for minimum weighted colorings of \((P_5, \overline{P}_5)\)-free graphs and similar graph classes
cites work: Q4448764
cites work: Vertex coloring of graphs with few obstructions
cites work: The coloring problem for classes with two small obstructions
cites work: Two cases of polynomial-time solvability for the coloring problem
cites work: Polynomial-time approximation algorithms for the coloring problem in some cases
cites work: Two complexity results for the vertex coloring problem
DOI: 10.1016/J.DAM.2018.04.006
Wikidata QID: Q129971205
description: scientific article; zbMATH DE number 6933535