Article
Full entry |
PDF
(0.3 MB)
Feedback
PDF
(0.3 MB)
Feedback
Keywords:
clique; chromatic number; isolated vertices; graph theory; graph colouring
clique; chromatic number; isolated vertices; graph theory; graph colouring
Summary:
In this paper, we show that the maximal number of minimal colourings of a graph with $n$ vertices and the chromatic number $k$ is equal to $k^{n-k}$, and the single graph for which this bound is attained consists of a $k$-clique and $n-k$ isolated vertices.
References:
[1] C. L. Liu: Introduction to Combinatoгial Mathematics. Mc Graw-Hill Book Co., New York, 1968. MR 0234840
Search
Partner of
