论文标题
Viping的边缘色定理的超模型扩展
Supermodular Extension of Vizing's Edge-Coloring Theorem
论文作者
论文摘要
Kőnig的边缘色定理用于两部分图和Vizing的Edge-loring定理用于一般图的庆祝结果和组合优化的结果。 Schrijver将kőnig的定理概括为用一对相交的超模块函数定义的框架。结果称为超模化定理。 本文介绍了Viping定理的共同概括，以及超模型定理的较弱版本。为了描述该定理，我们介绍了相交的2/3旋转函数，这是相交超模样函数的扩展。该论文还使用此超模型版本的Viping定理的特殊情况提供了Gupta的边缘色定理的替代证明。
Kőnig's edge-coloring theorem for bipartite graphs and Vizing's edge-coloring theorem for general graphs are celebrated results in graph theory and combinatorial optimization. Schrijver generalized Kőnig's theorem to a framework defined with a pair of intersecting supermodular functions. The result is called the supermodular coloring theorem. This paper presents a common generalization of Vizing's theorem and a weaker version of the supermodular coloring theorem. To describe this theorem, we introduce intersecting 2/3-supermodular functions, which are extensions of intersecting supermodular functions. The paper also provides an alternative proof of Gupta's edge-coloring theorem using a special case of this supermodular version of Vizing's theorem.
