论文标题
科尼格边缘定理的逻辑强度
The logical strength of König's edge coloring theorem
论文作者
论文摘要
König'sEdge Colorem Theorem说，具有最大程度$ n $的两部分图具有不超过$ n $颜色的边缘着色。我们探讨了该定理的计算性理论和反向数学方面。具有$ n $界限的度量的可计算的两分图具有$ n+1 $颜色的可计算边缘着色，但是定理的带有$ n $颜色的边缘着色等于wklo而不是rcao。这给出了hirst定理的额外证明：WKLO等同于RCAO与以下原则：每个可计数的两分$ n $ regular Graph是$ n $完整匹配的结合。我们描述了与Viping's Edge Cornorem和Birkhoff定理的可数形式有关的开放问题。
König's edge coloring theorem says that a bipartite graph with maximal degree $n$ has an edge coloring with no more than $n$ colors. We explore the computability theory and Reverse Mathematics aspects of this theorem. Computable bipartite graphs with degree bounded by $n$ have computable edge colorings with $n+1$ colors, but the theorem that there is an edge coloring with $n$ colors is equivalent to WKLo over RCAo. This gives an additional proof of a theorem of Hirst: WKLo is equivalent over RCAo to the principle that every countable bipartite $n$-regular graph is the union of $n$ complete matchings. We describe open questions related to Vizing's edge coloring theorem and a countable form of Birkhoff's theorem.
