A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. Let p(G) be the least number of colors in an edge-coloring of G having no parity path (a parity edge-coloring). Let p(G) be the least number of colors in an edge-coloring of G having no open parity walk (a strong parity edge-coloring). Always p(G) > p(G) > X'(G) We prove that p(Kn) = 2^n^ - 1 for all n The optimal strong parity edge-coloring of Kn is unique when n is a power of 2, and the optimal colorings are completely described for all n.
展开▼
机译：图的边缘着色中的奇偶校验步是沿着每种颜色使用偶数次的步。令p（G）是没有奇偶校验路径的G的边缘着色（奇偶校验边缘着色）中最少的颜色。令p（G）是没有开放奇偶校验游走的G的边缘着色（强奇偶校验边缘着色）中最少的颜色。总是p（G）> p（G）> X'（G）我们证明p（Kn）= 2 ^ n ^-1对于所有n当n是n的幂时，Kn的最佳强奇偶校验边着色是唯一的参见图2，并且针对所有n完全描述了最佳着色。
展开▼
