关于图的邻和可区别全染色的新方法

作者：常景智; 杨超^*; 姚兵

来源：山东大学学报(理学版), 2023, 58(06): 35-39.

• 非正常全染色
• 消圈集
• 邻和可区别全染色
• 1-2猜想

给出树的邻和可区别2-全染色方案，并结合三正则图最小消圈集的独立性以及消圈子图的无圈性，较为简洁地证明三正则图的邻和可区别全色数满足1-2猜想。进一步利用独立消圈集法确定r-正则图、Halin图以及路与路的笛卡尔乘积图的邻和可区别全色数。

• 单位
  西北师范大学; 上海工程技术大学