A sequential coloring algorithm for finite sets (Q1297462)

Let \(X\) be a finite set and \(P\) a hereditary property associated with the subsets of \(X\). A partition of \(X\) into \(n\) subsets each with property \(P\) is said to be a \(P\)-\(n\)-coloring of \(X\). The minimum \(n\) such that a \(P\)-\(n\)-coloring of \(X\) exists is defined to be the \(P\)-chromatic number of \(X\), denoted by \(\chi _{P}(X)\). The main purpose of this paper is to give an algorithm for sequentially \(P\)-coloring the finite set \(X\). By using this algorithm several upper bounds for \(\chi _{P}(X)\) are obtained; in particular, the well-known Welsh-Powell upper bound for the ordinary chromatic number is extended to the case of the \(P\)-chromatic number of any finite set. Also, the upper bounds obtained for \(P\)-chromatic numbers imply a theorem of the reviewer on the chromatic number of a hypergraph.