Parity and strong parity edge-colorings of graphs
Journal
Journal of Combinatorial Optimization
Journal Volume
24
Journal Issue
4
Pages
427-436
Date Issued
2012
Author(s)
Abstract
A parity walk in an edge-coloring of a graph is a walk along which each color is used an even number of times. A parity edge-coloring (respectively, strong parity edge-coloring) is an edge-coloring in which there is no nontrivial parity path (respectively, open parity walk). The parity edge-chromatic number p(G) (respectively, strong parity edge-chromatic number Δp(G)) is the least number of colors in a parity edge-coloring (respectively, strong parity edge-coloring) of G. Notice that Δp(G) ≥ p(G) ≥ χΔ (G) ≥ Δ (G) for any graph G. In this paper, we determine Δp(G) and p(G) for some complete bipartite graphs and some products of graphs. For instance, we determine Δp(Km,n) and p(Km,n) for m ≤ n with n Δ 0,-1,-2 (mod 2ΔlgmΔ). © Springer Science+Business Media, LLC 2011.
Type
journal article