The complexity of \(G\)-free colourability
type: Item
instance of: scholarly article
title: The complexity of \(G\)-free colourability
zbMATH Open document ID: 0904.05030
DOI: 10.1016/S0012-365X(97)84217-3
author: D. Achlioptas
published in: Discrete Mathematics
publication date: 1998-11-05T00:00:00Z
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 68Q25
Mathematics Subject Classification ID: 68R10
zbMATH DE Number: 1019082
zbMATH Keywords: chromatic number
zbMATH Keywords: 2-colourable
zbMATH Keywords: polynomial time algorithm
zbMATH Keywords: bipartition
zbMATH Keywords: NP-complete
MaRDI profile type: Publication
cites work: The existence of uniquely \(-G\) colourable graphs
cites work: On generalized graph colorings
cites work: Q3351379
cites work: ON UNIQUELY -G k-COLOURABLE GRAPHS
cites work: Q4100121
cites work: Q5560916
cites work: The point-arboricity of a graph
cites work: Q4198056
cites work: Graphs with unique Ramsey colorings
cites work: Q3220612
cites work: Q4111618
cites work: Q5613120
Recommended article: Complexity of colouring problems restricted to unichord-free and square, unichord-free graphs
Recommended article: Complexity of Grundy coloring and its variants
Recommended article: Nordhaus–Gaddum problem in terms of G-free coloring
Recommended article: Narrowing Down the Gap on the Complexity of Coloring P k -Free Graphs
Recommended article: The complexity of some graph colouring problems
Recommended article: Complexity of conflict-free colorings of graphs
Recommended article: The complexity of generalized graph colorings
Recommended article: Narrowing the Complexity Gap for Colouring (C s ,P t )-Free Graphs
Recommended article: Complexity of conditional colorability of graphs
description: scientific article; zbMATH DE number 1019082