The complexity of some problems related to GRAPH 3-COLORABILITY
type: Item
instance of: scholarly article
title: The complexity of some problems related to GRAPH 3-COLORABILITY
zbMATH Open document ID: 0927.68063
DOI: 10.1016/S0166-218X(98)00116-4
author: Andreas Brandstädt
author: Van Bang Le
author: Thomas Szymczak
published in: Discrete Applied Mathematics
publication date: 1999-03-22T00:00:00Z
Mathematics Subject Classification ID: 68R10
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 1267542
zbMATH Keywords: graph 3-colorability problem
MaRDI profile type: Publication
cites work: Partitions of graphs into one or two independent sets and cliques
cites work: A generalization of perfect graphs?i-perfect graphs
cites work: The Complexity of Near-Optimal Graph Coloring
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: The ellipsoid method and its consequences in combinatorial optimization
cites work: Q3216686
cites work: The splittance of a graph
cites work: Q4142699
cites work: Q4083461
cites work: On the NP-completeness of the \(k\)-colorability problem for triangle-free graphs
cites work: Threshold graphs and related topics
cites work: The complexity of satisfiability problems
full work available at URL: s0166-218x(98)00116-4
OpenAlex ID: W2050157065
description: scientific article; zbMATH DE number 1267542