The strength of König's edge coloring theorem
Carl Mummert (Marshall University)
Abstract: König's edge coloring theorem says that a bipartite graph with maximal degree has an edge coloring with no more than colors. We study the computability theory and Reverse Mathematics of this theorem. Computable bipartite graphs with degree bounded by have computable edge colorings with colors, but the theorem that there is an edge coloring with colors is equivalent to over . The number of colors permitted affects the computability of the solution. We obtain an additional proof of the following theorem of Paul Shafer: is equivalent over to the principle that a countable bipartite n-regular graph is the union of n complete matchings.
combinatoricslogic
Audience: researchers in the topic
Series comments: Description: Seminar on all areas of logic
Organizer: | Wesley Calvert* |
*contact for this listing |