Mathematical Theory and Applications ›› 2026, Vol. 46 ›› Issue (03): 69-82.doi: 10.3969/j.issn.1006-8074.2026.03.005
Previous Articles Next Articles
Tian Junyi , Wen Chao , Cai Hongyan, Zhang Chao*
Online:
Published:
Supported by:
Abstract: This paper investigates the edge coloring classification of signed complete bipartite graphs $(K_{2^n,2^n},\sigma)$, with the aim of verifying the conjecture proposed by Janczewski et al: $(K_{r,r},\sigma)$ is Class 1 if and only if $r$ is odd, or $r$ is even and the number of negative edges is even. We prove this conjecture for the case $r=2^n$. Methodologically, we first simplify the sign structure of $(K_{4,4},\sigma)$ via switching equivalence, and then establish its Class 1 criterion by means of Hamiltonian cycle decomposition and isomorphism classification. Based on this, we apply an inductive construction: partition the general case into subblocks, adjust the parity of negative edges in each subblock via vertex exchanges, and finally color each subblock independently and merge the color sets to complete the induction. The results show that $(K_{2^n,2^n},\sigma)$ ($n\ge2$) is Class 1 if and only if the total number of negative edges is even, which verifies the conjecture of Janczewski et al. for the case $r=2^n$ and provides new theoretical evidence for the complete classification of the chromatic index of signed complete bipartite graphs.
Key words: Signed graph, Edge coloring, Complete bipartite graph
Tian Junyi , Wen Chao , Cai Hongyan, Zhang Chao. Edge Coloring of Signed Complete Bipartite Graphs $(K_{2^n, 2^n},\sigma)$[J]. Mathematical Theory and Applications, 2026, 46(03): 69-82.
0 / / Recommend
Add to citation manager EndNote|Ris|BibTeX
URL: https://mta.csu.edu.cn/EN/10.3969/j.issn.1006-8074.2026.03.005
https://mta.csu.edu.cn/EN/Y2026/V46/I03/69