数学理论与应用 ›› 2026, Vol. 46 ›› Issue (03): 69-82.doi: 10.3969/j.issn.1006-8074.2026.03.005

• • 上一篇    下一篇

符号完全二部图 $(K_{2^n, 2^n},\sigma)$ 的边着色

田俊逸, 文超, 蔡红艳,  章超*   

  1. 贵州大学数学与统计学院,贵阳 550025
  • 出版日期:2026-09-28 发布日期:2026-11-02
  • 通讯作者: 章超
  • 基金资助:
    本文得到国家自然科学基金项目(No. 12461006)资助

Edge Coloring of Signed Complete Bipartite Graphs $(K_{2^n, 2^n},\sigma)$

Tian Junyi , Wen Chao , Cai Hongyan, Zhang Chao*   

  1. School of Mathematics and Statistics, Guizhou University, Guiyang 550025, China
  • Online:2026-09-28 Published:2026-11-02
  • Supported by:

摘要: 本文研究符号完全二部图 $(K_{2^n,2^n},\sigma)$ 的边着色分类问题,旨在验证 Janczewski 等人提出的猜想: $(K_{r,r},\sigma)$ 为第一类当且仅当 $r$ 为奇数,或 $r$ 为偶数且负边总数为偶数.本文针对 $r=2^n$ 的情形证明该猜想.方法上,首先通过切换等价化简 $(K_{4,4},\sigma)$ 的符号结构,再借助哈密顿圈分解与同构分类建立其第一类判定准则;以此为基础,采用归纳构造,将一般情形划分为若干子块,并通过顶点交换调整各子块负边奇偶性,最终对各子块独立着色并合并颜色集,完成归纳证明.结果表明, $(K_{2^n,2^n},\sigma)$ $(n\ge2$)为第一类当且仅当负边总数为偶数.该结果验证了 Janczewski 等人在 $r=2^n$ 情形下的猜想,为符号完全二部图边色数的完整分类提供了新的理论依据.

关键词: 符号图, 边着色, 完全二部图

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