Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



A uniform set covering lemma

Author: David W. Matula
Journal: Proc. Amer. Math. Soc. 48 (1975), 255-261
MSC: Primary 05B40
MathSciNet review: 0376408
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: The bounded set system $ H = (V,\mathfrak{F})$ is composed of a nonvoid set $ V$ and a set, $ \mathfrak{F}$, of nonvoid subsets of $ V$, a finite number of which cover $ V$. $ C \subset V$ is a critical subset of $ H$ if every proper subset of $ C$ requires fewer members of $ \mathfrak{F}$ to cover it than are needed to cover $ C$. For $ \vert\mathfrak{F}\vert$ finite, it is shown that every $ A \subset V$ contains a critical $ C \subset A$ requiring the same number of members of $ \mathfrak{F}$ in a minimum cover. For $ v \in V,l(v)$ is the largest number of members of $ \mathfrak{F}$ in any minimum cover of any critical set containing $ v$. For $ \vert\mathfrak{F}\vert$ finite, it is shown that there exists a covering $ {A_1},{A_2}, \cdots ,{A_k},{A_i} \in \mathfrak{F}$ for $ 1 \leq i \leq k$, such that $ v \in \bigcup\nolimits_{i = 1}^{l(v)} {{A_i}} $ for all $ v \in V$. An application to graph coloring is described.

References [Enhancements On Off] (What's this?)

  • [1] Claude Berge, Graphes et hypergraphes, Dunod, Paris, 1970 (French). Monographies Universitaires de Mathématiques, No. 37. MR 0357173
  • [2] G. A. Dirac, The structure of 𝑘-chromatic graphs, Fund. Math. 40 (1953), 42–55. MR 0060207
  • [3] Richard M. Karp, Reducibility among combinatorial problems, Complexity of computer computations (Proc. Sympos., IBM Thomas J. Watson Res. Center, Yorktown Heights, N.Y., 1972) Plenum, New York, 1972, pp. 85–103. MR 0378476
  • [4] D. W. Matula, Bounded color functions on graphs, Networks 2 (1972), 29–44. MR 0297627
  • [5] Oystein Ore, The four-color problem, Pure and Applied Mathematics, Vol. 27, Academic Press, New York-London, 1967. MR 0216979

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC: 05B40

Retrieve articles in all journals with MSC: 05B40

Additional Information

Keywords: Set coverings, critical sets, minimum covers, uniform cover, hypergraph, graph covering, Grundy function
Article copyright: © Copyright 1975 American Mathematical Society