The strength of König's edge coloring theorem

Abstract: 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 study the computability theory and Reverse Mathematics of this theorem. Computable bipartite graphs with degree bounded by $n$ have computable edge colorings with $2n-1$ colors, but the theorem that there is an edge coloring with $n$ colors is equivalent to $\mathsf{WKL}_0$ over $\mathsf{RCA}_0$. The number of colors permitted affects the computability of the solution. We obtain an additional proof of the following theorem of Paul Shafer: $\mathsf{WKL}_0$ is equivalent over $\mathsf{RCA}_0$ to the principle that a countable bipartite n-regular graph is the union of n complete matchings.

combinatoricslogic

Audience: researchers in the topic

Online logic seminar

Series comments: Description: Seminar on all areas of logic