Hostname: page-component-586b7cd67f-l7hp2 Total loading time: 0 Render date: 2024-11-20T16:36:27.696Z Has data issue: false hasContentIssue false

On the Basis and Chromatic Number of a Graph

Published online by Cambridge University Press:  20 November 2018

C. J. Everett*
Affiliation:
Los Alamos, New Mexico
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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*.

Type
Research Article
Copyright
Copyright © Canadian Mathematical Society 1966

References

1. Berge, C., Theory of graphs (New York, 1964).Google Scholar
2. Birkhoff, G., Lattice theory (Providence, 1948).Google Scholar
3. Lefschetz, S., Algebraic topology (Providence, 1942).Google Scholar
4. Ore, O., Theory of graphs (Providence, 1962).Google Scholar