On the ratio of optimal integral and fractional covers. (English) Zbl 0323.05127


05C99 Graph theory
05C15 Coloring of graphs and hypergraphs
Full Text: DOI


[1] J. Peck, oral communication.
[2] Berge, C., Graphs and hypergraphs, (1973), North-Holland Amsterdam · Zbl 0483.05029
[3] Edmonds, J., Sub modular functions, matroids and certain polyhedra, (), 69-87
[4] Erdös, P., On a combinatorial problem II, Acta math. acad. sci. hungar., 15, 445-447, (1964) · Zbl 0201.33704
[5] Gallai, T., Maximum-minimum Sätze und verallgemeinerte faktoren von graphen, Acta math. acad. sci. hungar., 12, 131-173, (1961) · Zbl 0142.41404
[6] Lorentz, G., On a problem in additive number theory, Proc. am. math. soc., 5, 838-841, (1954) · Zbl 0056.03902
[7] Lovász, L., Normal hypergraphs and the perfect graph conjecture, Discrete math., 2, 253-267, (1972) · Zbl 0239.05111
[8] L. Lovász, 2-matchings and 2-covers of hypergraphs, to appear.
[9] C. Luchesi and D.H. Younger, A minimax theorem for directed graphs, to appear.
[10] McEliece, R.J.; Posner, E.C., Hide and seek, data storage, and entropy, Am. statist., 42, 1706-1716, (1971) · Zbl 0235.05001
[11] Rosenfeld, M., On a problem of C.E. Shannon in graph theory, Proc. am. math. soc., 18, 315-319, (1967) · Zbl 0147.42801
[12] S. Stahl, n-tuple colorings and associated graphs, J. Combin. Theory, to appear. · Zbl 0293.05115
[13] Vizing, V.G.; Berge, C., Graphs and hypergraphs, Diskret. analiz., 3, 25-30, (1973), North-Holland Amsterdam, (in Russian);
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.