NP-completeness of local colorings of graphs
type: Item
instance of: scholarly article
title: NP-completeness of local colorings of graphs
zbMATH Open document ID: 1419.68055
author: Zepeng Li
author: Zehui Shao
author: Jin Xu
author: Enqiang Zhu
published in: Information Processing Letters
publication date: 2017-11-22T00:00:00Z
Mathematics Subject Classification ID: 68Q17
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 6810897
zbMATH Keywords: local \(k\)-coloring
zbMATH Keywords: local chromatic number
zbMATH Keywords: planar graph
zbMATH Keywords: NP-complete
zbMATH Keywords: computational complexity
MaRDI profile type: Publication
full work available at URL: j.ipl.2017.09.013
OpenAlex ID: W2759840798
cites work: Q5422499
cites work: Q5461691
cites work: Q4472717
cites work: The complexity of theorem-proving procedures
cites work: Coloring graphs with locally few colors
cites work: Q4198056
cites work: A generalization of Kneser's conjecture
cites work: Q4857375
cites work: Reducibility among Combinatorial Problems
cites work: Local colourings of Cartesian product graphs
cites work: A note on local coloring of graphs
cites work: Q3070244
cites work: Local coloring of Kneser graphs
DOI: 10.1016/J.IPL.2017.09.013
Recommended article: Q3070244
Recommended article: The complexity of colouring by locally semicomplete digraphs
Recommended article: Local and global colorability of graphs
Recommended article: Q5461691
Recommended article: On the complexity of graph coloring with additional local conditions
Recommended article: A note on local coloring of graphs
Recommended article: A note on local colorings of graphs
Recommended article: Coloring graphs with locally few colors
Recommended article: Generalized local colorings of graphs
Recommended article: Local \(k\)-colorings of graphs and hypergraphs
description: scientific article; zbMATH DE number 6810897