Parity and strong parity edge-colorings of graphs |
| |
Authors: | Hsiang-Chun Hsu Gerard J. Chang |
| |
Affiliation: | 1. Department of Mathematics, National Taiwan University, Taipei, 10617, Taiwan 2. Taida Institute for Mathematical Sciences, National Taiwan University, Taipei, 10617, Taiwan 3. National Center for Theoretical Sciences, Taipei, Taiwan
|
| |
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 $widehat{p}(G)$ ) is the least number of colors in a parity edge-coloring (respectively, strong parity edge-coloring) of G. Notice that $widehat{p}(G) ge p(G) ge chi'(G) ge Delta(G)$ for any graph G. In this paper, we determine $widehat{p}(G)$ and p(G) for some complete bipartite graphs and some products of graphs. For instance, we determine $widehat{p}(K_{m,n})$ and p(K m,n ) for m≤n with n≡0,?1,?2 (mod 2?lg?m?). |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|