论文标题
关于完美2色的极端特性
On extremal properties of perfect 2-colorings
论文作者
论文摘要
如果对于每个顶点，其邻居的颜色集合仅取决于其自身的颜色，则将图的颜色称为完美。顶点的通讯颜色分区称为公平。我们注意到，仅在完美的$ 2 $颜色上达到了许多界限（Hoffman Bound，Cheeger Bound，Bierbrauer-Friedman Bound和其他）。我们证明，膨胀液混合引理是不平等的另一个例子，它产生了完美的$ 2 $颜色。我们证明了$ s \ subset v（g）$的新上限，具有固定的平均内部学位，适用于常规的图形$ g $。当$ \ {s，v（g）\ setMinus s \} $是一个公平分区时，仅在集合$ s $上达到此限制。
A coloring of vertices of a graph is called perfect if, for every vertex, the collection of colors of its neighbors depends only on its own color. The correspondent color partition of vertices is called equitable. We note that a number of bounds (Hoffman bound, Cheeger bound, Bierbrauer--Friedman bound and other) is only reached on perfect $2$-colorings. We show that the Expander Mixing Lemma is another example of an inequality that generates a perfect $2$-coloring. We prove a new upper bound for the size of $S\subset V(G)$ with the fixed average internal degree for an amply regular graph $G$. This bound is reached on the set $S$ if and only if $\{S, V(G)\setminus S\}$ is an equitable partition.
