On the injective chromatic number of graphs
type: Item
instance of: scholarly article
title: On the injective chromatic number of graphs
zbMATH Open document ID: 1007.05046
DOI: 10.1016/S0012-365X(01)00466-6
author: Geňa Hahn
author: Jan Kratochvíl
author: Jozef Širáň
author: D. Sotteau
published in: Discrete Mathematics
publication date: 2002-12-02T00:00:00Z
review text: A vertex \(k\)-coloring of a graph is said to be injective if its restriction to the neighbourhood of any vertex is injective. The injective chromatic number of a graph \(G\) is the least \(k\) such that there is an injective \(k\)-coloring of \(G\). In this paper some upper and lower bounds in general, plus some exact values are given. In particular, the injective chromatic number of the hypercube is explored in the context of previous work on similar concepts, especially the theory of error-correcting codes. Necessary and sufficient conditions for the injective chromatic number to be equal to the degree for a regular graph are proposed and it is shown that the problem of determining whether there exists an injective \(k\)-coloring of a graph \(G\) is NP-complete for every fixed \(k\geq 3\).
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1838919
zbMATH Keywords: injective chromatic number
zbMATH Keywords: injective coloring
zbMATH Keywords: hypercube
zbMATH Keywords: regular graph
zbMATH Keywords: error-correcting code
zbMATH Keywords: projective plane
zbMATH Keywords: NP-complete problem
Wikidata QID: Q114122944
reviewed by: Ioan Tomescu
MaRDI profile type: Publication
full work available at URL: s0012-365x(01)00466-6
OpenAlex ID: W2125862453
Recommended article: Some results on the injective chromatic number of graphs
Recommended article: Some bounds on the injective chromatic number of graphs
Recommended article: On injective chromatic polynomials of graphs
Recommended article: On Injective Colourings of Chordal Graphs
Recommended article: Injective chromatic number of outerplanar graphs
Recommended article: Injective coloring of graphs revisited
Recommended article: Q3381809
Recommended article: Critical injective chromatic graphs
Recommended article: Q5020302
Recommended article: Q5143274
description: scientific article; zbMATH DE number 1838919