On an Edge Precoloring Conjecture

Abstract

Edwards, van den Heuvel, Kang, and Sereni conjectured the following strengthening of Vizing's Theorem: let $G$ be a simple graph, and let $K=\Delta (G)+1$. For any matching $M$ in $G$ and any precoloring of the edges in $M$ using the colors $\{1,\dots ,K\}$, there is some proper $K$-edge-coloring of $G$ extending the given precoloring. We give an infinite family of counterexamples to this conjecture, and prove a weaker version of the conjecture proposed in the same work.

The construction in this article has now been incorporated into arXiv:1407.4339 and the conjecture updated accordingly. As such, this article is now obsolete

References in corpus (1)

• Maximal $k$-Edge-Colorable Subgraphs, Vizing's Theorem, and Tuza's Conjecture