A generalization of the chromatic number
- 1 April 1968
- journal article
- Published by Cambridge University Press (CUP) in Mathematical Proceedings of the Cambridge Philosophical Society
- Vol. 64 (2) , 265-271
- https://doi.org/10.1017/s0305004100042808
Abstract
One of the most widely studied concepts in graph theory is that of the colouring of graphs. Much of the research in this area has dealt with the chromatic number χ(G) of a graph G, defined as the minimum number of colours which can be assigned to the points of G so that adjacent points are coloured differently. One can obtain a natural generalization of this concept as follows: we define the n-chromatic number χn (G) to be the smallest number of colours which one can associate with the points of G so that not all points on any path of length n are coloured the same. The 1-chromatic number is then simply the chromatic number.This publication has 0 references indexed in Scilit: