Previous |  Up |  Next


chromatic number; connected graph; colouring of a graph; $k$-chromatic graphs; independent set
In this paper we characterize $k$-chromatic graphs without isolated vertices and connected $k$-chromatic graphs having a minimal number of edges.
[1] C. Berge: Graphes et Hypergraphes. Dunod, Paris, 1970. MR 0357173 | Zbl 0213.25702
[2] N. Christofides: Graph Theory - An Algorithmic Approach. Academic Press, New York, 1975. MR 0429612 | Zbl 0321.94011
[3] A. Ershov, G. Kuzhukhin: Estimates of the chromatic number of connected graphs. Dokl. Akad. Nauk. 142, 2 (1962), 270-273. (In Russian.) MR 0140445
Partner of
EuDML logo