On the Basis and Chromatic Number of a Graph
Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 969-973
Voir la notice de l'article provenant de la source Cambridge University Press
The basis theorem for directed graphs is, in effect, a result on weakly ordered sets, and, in §1, a proof is given, based on Zorn's lemma, that generalizes, and perhaps clarifies the exposition in (1, Chapter 2). In §2, a graph G* is defined, on an arbitrary collection Q of non-void subsets of a set X (which includes all its one-element subsets), in such a way that the partitions of X into Q-sets correspond to the kernels of G*. Applied to the collection Q of non-null internally stable subsets of a graph G without loops, this identifies the chromatic number of G with the least cardinal number of any kernel of G*.
Everett, C. J. On the Basis and Chromatic Number of a Graph. Canadian journal of mathematics, Tome 18 (1966) no. 1, pp. 969-973. doi: 10.4153/CJM-1966-097-6
@article{10_4153_CJM_1966_097_6,
author = {Everett, C. J.},
title = {On the {Basis} and {Chromatic} {Number} of a {Graph}},
journal = {Canadian journal of mathematics},
pages = {969--973},
year = {1966},
volume = {18},
number = {1},
doi = {10.4153/CJM-1966-097-6},
url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1966-097-6/}
}
[1] 1. Berge, C., Theory of graphs (New York, 1964). Google Scholar
[2] 2. Birkhoff, G., Lattice theory (Providence, 1948). Google Scholar
[3] 3. Lefschetz, S., Algebraic topology (Providence, 1942). Google Scholar
[4] 4. Ore, O., Theory of graphs (Providence, 1962). Google Scholar
Cité par Sources :