Parity and Strong Parity Edge-Coloring of Graphs

摘要

A parity walk in an edge-coloring of a graph is a walk using each color an even number of times. Let p(G) be the least number of colors in a parity edge-coloring of G (a coloring having no parity path). Let p(G) be the least number in a strong parity edge-coloring of G (one with no open parity walk). Note that p(G) ≥ p(G) ≥ χ'(G)-The values p(G) and p(G) may be equal or differ; we conjecture equality for bipartite graphs. If G is connected, then p(G) ≥ [lg |V(G)|], with equality for paths and even cycles (one more color for odd cycles). The proof that p(K_n) = 2~([lg n]) - 1 for all n will appear later; the conjecture that p(K_n) = p(K_n) is proved here for n ≤ 16 and other cases. Also, p(K_(2,n)) - p(K_(2,n)) = 2 [n/2]. In general, p(K_(m,n)) ≤ m' [n/m'], where m' = 2~([lg m]). We compare these parameters to others and pose many open questions.