zbMATH — the first resource for mathematics

About vertex-critical non-bicolorable hypergraphs. (English) Zbl 0842.05069
Summary: The hypergraphs whose chromatic number is \(\leq 2\) (“bicolorable” hypergraphs) were introduced by E. W. Miller under the name of “set-systems with property B”. This concept appears in number theory. It is also useful for some problems in positional games and operations research; different results have been found in the form of inequalities involving the sizes of the edges, the number of vertices, etc. A non-bicolorable hypergraph which becomes bicolorable when any of its edges is removed is called “edge-critical”, and several of its properties can be found in the literature. In this paper, instead of edge-critical hypergraphs, we study the vertex-critical hypergraphs; the applications are more numerous, and it seems that somewhat stronger results could imply the famous “four-color theorem”.

05C65 Hypergraphs
05C15 Coloring of graphs and hypergraphs