On vertex-parity edge-colorings |
| |
Authors: | Borut Lužar Mirko Petruševski Riste Škrekovski |
| |
Institution: | 1.Faculty of Information Studies,Novo Mesto,Slovenia;2.Department of Mathematics and Informatics,Faculty of Mechanical Engineering-Skopje,Skopje,Republic of Macedonia;3.Institute of Mathematics,Physics and Mechanics,Ljubljana,Slovenia;4.University of Primorska, FAMNIT,Koper,Slovenia |
| |
Abstract: | A vertex signature \(\pi \) of a finite graph G is any mapping \(\pi \,{:}\,V(G)\rightarrow \{0,1\}\). An edge-coloring of G is said to be vertex-parity for the pair \((G,\pi )\) if for every vertex v each color used on the edges incident to v appears in parity accordance with \(\pi \), i.e. an even or odd number of times depending on whether \(\pi (v)\) equals 0 or 1, respectively. The minimum number of colors for which \((G,\pi )\) admits such an edge-coloring is denoted by \(\chi '_p(G,\pi )\). We characterize the existence and prove that \(\chi '_p(G,\pi )\) is at most 6. Furthermore, we give a structural characterization of the pairs \((G,\pi )\) for which \(\chi '_p(G,\pi )=5\) and \(\chi '_p(G,\pi )=6\). In the last part of the paper, we consider a weaker version of the coloring, where it suffices that at every vertex, at least one color appears in parity accordance with \(\pi \). We show that the corresponding chromatic index is at most 3 and give a complete characterization for it. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|