Partition into cliques for cubic graphs: Planar case, complexity and approximation
type: Item
instance of: scholarly article
title: Partition into cliques for cubic graphs: Planar case, complexity and approximation
zbMATH Open document ID: 1144.05049
author: T. O. Ferreira
author: C. A. J. Martinhon
author: Márcia R. Cerioli
author: Luerbio Faria
author: Fábio Protti
author: Bruce Reed
published in: Discrete Applied Mathematics
publication date: 2008-09-29T00:00:00Z
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C35
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 5348228
zbMATH Keywords: NP-complete
zbMATH Keywords: Max SNP-hard
zbMATH Keywords: partition into cliques
zbMATH Keywords: coloring
zbMATH Keywords: approximation
zbMATH Keywords: cubic planar graphs
MaRDI profile type: MaRDI publication profile
full work available at URL: j.dam.2007.10.015
OpenAlex ID: W1985638002
cites work: Q4258216
cites work: Free Bits, PCPs, and Nonapproximability---Towards Tight Results
cites work: Q5782525
cites work: Paths, Trees, and Flowers
cites work: Q4198056
cites work: Some simplified NP-complete graph problems
cites work: A still better performance guarantee for approximate graph coloring
cites work: Approximating k-set cover and complementary graph coloring
cites work: The Complexity of Planar Counting Problems
cites work: Q4142699
cites work: Q4228486
cites work: Planar Formulae and Their Uses
cites work: Optimization, approximation, and complexity classes
cites work: Q3221403
DOI: 10.1016/J.DAM.2007.10.015
description: scientific article; zbMATH DE number 5348228