Problems and Results on 3-chromatic Hypergraphs and Some Related Questions
Problems and Results on 3-chromatic Hypergraphs and Some Related Questions
复制标题
DOI：
--
复制
发表时间：
--
期刊：
影响因子：
--
通讯作者：
P. Erdos-L Lovász
中科院分区：
文献类型：
--
作者：
P. Erdos-L Lovász
超图是集合的集合。本文仅涉及有限超图。超图中的集合称为边，这些边的元素是点。点的度是包含该点的边的数量。如果每条边都有 r 个点，则超图是 r 均匀的。如果任意两条边最多有一个公共点，则超图是简单的；如果任意两条边至少有一个公共点，则称为团。超图的色数是最小的数 k，使得点可以是 k 色的，从而没有边是单色的。据我们所知，色数为 2 的集合族首先由 M i 11 e r（使用术语属性 B）在无限边的情况下系统地研究。现在有大量关于有限集和无限集的主题的文献。我们研究背后的主要思想是，简单或派系对三色超图施加了令人惊讶的严格属性。
A hypergraphi is a collection of sets. This paper deals with finite hy-pergraphs only. The sets in the hypergraph are called edges, the elements of these edges are points. The degree of a point is the number of edges containing it. The hypergraph is r-uniform if every edge has r points. A hypergraph is simple if any two edges have at most one common point, and it is called a clique if any two edges have at least one common point. The chromatic number of a hypergraph is the least number k such that the points can be k-colored so that no edge is monochromatic. As far as we know families of sets with chromatic number 2 were first investigated systematically by M i 11 e r (who used the term property B) in the case of infinite edges. There now is a large literature of this subject both for finite and infinite sets. The main idea behind our investigations is that being simple or being a clique imposes surprisingly strict properties on 3-chromatic hypergraphs .