The notion of coloring number of a graph was introduced by P. Erdo s and A. Hajnal in [2] in order to investigate the chromatic number of infinite graphs. For a graph G its coloring number, Col(G) is defined to be the least cardinal } for which there is a well ordering of the vertex set in which every vertex is joined to less than } smaller vertices. This makes it possible to color the vertices by } colors via a straightforward transfinite induction. The chromatic number of a graph G, Chr(G) is the least cardinal } such that the vertex set can be colored with } colors. It is then straightforward that the chromatic number is at most the coloring number. But in general, it can be much smaller; there are bipartite graphs with arbitrary large coloring number. Several statements true for the chromatic number are true for the coloring number as well and there are numerous examples when a natural question has a yes'' answer for the coloring number while it has a no'' answer for the chromatic number. For example, Shelah's Singular Cardinal Compactness Theorem states that if G is a graph on a vertex set of some singular cardinal * and every subgraph of smaller cardinality has coloring number + for some cardinal + then Col(G) + ([8]). This fails for the chromatic number ([9]). There is, however, an interesting exception to the above general rule.
As an early application of the so called compactness principles de Bruijn and Erdo s proved [1] that the chromatic number, if finite, is attained by a finite subgraph. (See an excellent exposition in [3].) This essentially reduces the theory of finite chromatic graphs to the theory of finite graphs. In [2], however, Erdo s and Hajnal observed that this is not the case for the coloring number: If the coloring number of every finite subgraph is at most k<| then the coloring number of the whole graph can be as large as 2k&2 and this is sharp. (See also [7].