The Open UniversitySkip to content
 

On the injective chromatic number of graphs

Hahn, G.; Kratochvil, J.; Sotteau, D. and Siran, J. (2002). On the injective chromatic number of graphs. Discrete Mathematics, 256(1-2) pp. 179–192.

DOI (Digital Object Identifier) Link: http://dx.doi.org/10.1016/S0012-365X(01)00466-6
Google Scholar: Look up in Google Scholar

Abstract

We define the concepts of an injective colouring and the injective chromatic number of a graph and give some upper and lower bounds in general, plus some exact values. We explore in particular the injective chromatic number of the hypercube and put it in the context of previous work on similar concepts, especially the theory of error-correcting codes. Finally, we give necessary and sufficient conditions for the injective chromatic number to be equal to the degree for a regular graph.

Item Type: Journal Article
ISSN: 0012-365X
Keywords: Graph colouring; Codes; Hypercube
Academic Unit/Department: Mathematics, Computing and Technology > Mathematics and Statistics
Item ID: 8094
Depositing User: Jozef Širáň
Date Deposited: 14 Jun 2007
Last Modified: 02 Dec 2010 20:00
URI: http://oro.open.ac.uk/id/eprint/8094
Share this page:

Altmetrics

Scopus Citations

Actions (login may be required)

View Item
Report issue / request change

Policies | Disclaimer

© The Open University   + 44 (0)870 333 4340   general-enquiries@open.ac.uk