论文标题
同时边缘着色的注释
A note on the simultaneous edge coloring
论文作者
论文摘要
令$ g =（v，e）$为图。 A（合适的）$ K $ - 边颜色是$ g $的边缘的着色，使得共享端点的任何一对边缘都会获得不同的颜色。 vize的经典结果可确保任何简单的图$ g $都承认$（δ（g）+1）$ - 边缘着色，其中$δ（g）$表示$ g $的最大degreee。最近，Cabello提出了以下问题：给定两张图$ g_1，g_2 $最高度$δ$在同一套顶点$ v $上，是否可以以$ g $的限制，以$ g $的限制，以$ g_1 $ $ g_1 $和$ g_2 $ g_2 $ g_2 $ colorings的限制，以$δ+2 $的颜色将其（边缘）结合起来？更一般而言，在给定$ \ ell $图的情况下，我们需要几种颜色来以这种方式限制对每个图的限制是正确的？ 在此简短说明中，我们证明我们始终可以将图形的结合$ g_1，\ ldots，g_ \ ell $最高度$δ$带有$ω$（\ sqrt {\ ell} \cdotΔ）$颜色，并且存在图形的图是构成的图形紧密且恒定的多重因子。此外，对于两个图，我们证明，最多$ \ frac32Δ+4 $颜色就足够了，据我们所知，这是最著名的上限。
Let $G=(V,E)$ be a graph. A (proper) $k$-edge-coloring is a coloring of the edges of $G$ such that any pair of edges sharing an endpoint receive distinct colors. A classical result of Vizing ensures that any simple graph $G$ admits a $(Δ(G)+1)$-edge coloring where $Δ(G)$ denotes the maximum degreee of $G$. Recently, Cabello raised the following question: given two graphs $G_1,G_2$ of maximum degree $Δ$ on the same set of vertices $V$, is it possible to edge-color their (edge) union with $Δ+2$ colors in such a way the restriction of $G$ to respectively the edges of $G_1$ and the edges of $G_2$ are edge-colorings? More generally, given $\ell$ graphs, how many colors do we need to color their union in such a way the restriction of the coloring to each graph is proper? In this short note, we prove that we can always color the union of the graphs $G_1,\ldots,G_\ell$ of maximum degree $Δ$ with $Ω(\sqrt{\ell} \cdot Δ)$ colors and that there exist graphs for which this bound is tight up to a constant multiplicative factor. Moreover, for two graphs, we prove that at most $\frac 32 Δ+4$ colors are enough which is, as far as we know, the best known upper bound.
