论文标题
Viping viping的多编码定理的预论扩展
Precoloring extension of Vizing's Theorem for multigraphs
论文作者
论文摘要
令$ g $为最高度$δ（g）$和最大乘数$μ（g）$的图。独立地证明了1960年代$ g $的色度最多是$δ（g）+μ（g）$。 $ g $中两个边缘$ e $和$ f $之间的距离是连接endvertex $ e $的最短路径和$ f $的endvertex。距离$ t $匹配是一组具有成对距离至少$ t $的边缘。 Edwards等。提出了以下猜想：对于任何图形$ g $，使用调色板$ \ {1，\ dots，δ（g）+μ（g）\} $，任何对距离$ 2 $匹配的预先切换都可以扩展到$ g $的适当边缘颜色。 Girão和Kang验证了这一猜想的距离-9美元$匹配。在本文中，我们将所需距离从$ 9 $提高到$ 3 $，用于$μ（g）\ ge 2 $。
Let $G$ be a graph with maximum degree $Δ(G)$ and maximum multiplicity $μ(G)$. Vizing and Gupta, independently, proved in the 1960s that the chromatic index of $G$ is at most $Δ(G)+μ(G)$. The distance between two edges $e$ and $f$ in $G$ is the length of a shortest path connecting an endvertex of $e$ and an endvertex of $f$. A distance-$t$ matching is a set of edges having pairwise distance at least $t$. Edwards et al. proposed the following conjecture: For any graph $G$, using the palette $\{1, \dots, Δ(G)+μ(G)\}$, any precoloring on a distance-$2$ matching can be extended to a proper edge coloring of $G$. Girão and Kang verified this conjecture for distance-$9$ matchings. In this paper, we improve the required distance from $9$ to $3$ for multigraphs $G$ with $μ(G) \ge 2$.
