首页 | 本学科首页   官方微博 | 高级检索  
     


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 mn with n≡0,?1,?2 (mod 2?lg?m?).
Keywords:
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号