论文标题
着色定向超图
Coloring directed hypergraphs
论文作者
论文摘要
灵感来自于早期关于超图的适当和多色着色的结果，我们研究了有向超图的色彩，即，每个高架的顶点都分为两个部分，一个尾巴和头部。我们提出了D.Pálvölgyi和作者的猜想，其中指出指示对其成对交叉点有一定限制的超图可以用两种颜色进行颜色。除其他贡献外，我们的主要结果是证明了这种猜想的$ 3 $均匀的指向超图。该结果可以等效地措辞，以便如果$ 3 $统一的指示超图避免了具有两个超琴的某些定向超图，则承认合适的$ 2 $颜色。以前，仅研究了避免特定超edge的有向超图的最大边缘数量的极端问题。
Inspired by earlier results about proper and polychromatic coloring of hypergraphs, we investigate such colorings of directed hypergraphs, that is, hypergraphs in which the vertices of each hyperedge is partitioned into two parts, a tail and a head. We present a conjecture of D. Pálvölgyi and the author, which states that directed hypergraphs with a certain restriction on their pairwise intersections can be colored with two colors. Besides other contributions, our main result is a proof of this conjecture for $3$-uniform directed hypergraphs. This result can be phrased equivalently such that if a $3$-uniform directed hypergraph avoids a certain directed hypergraph with two hyperedges, then it admits a proper $2$-coloring. Previously, only extremal problems regarding the maximum number of edges of directed hypergraphs that avoid a certain hyperedge were studied.
