On the Basis and Chromatic Number of a Graph

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 collectionQof non-void subsets of a setX(which includes all its one-element subsets), in such a way that the partitions ofXintoQ-sets correspond to the kernels ofG*.Applied to the collectionQof non-null internally stable subsets of a graphGwithout loops, this identifies the chromatic number ofGwith the least cardinal number of any kernel ofG*.