完全三部图的点可约全染色

作者：雷飞; 李沐春^*

来源：武汉大学学报(理学版), 2022, 68(05): 471-478.

DOI：10.14188/j.1671-8836.2021.0343

• 完全三部图
• 全染色
• 点可约全染色
• 点可约全色数

设f:V(G)∪E (G)→{1,?,k}是图G的一个(非正常)k-全染色,其中1≤k≤Δ+1。若对任意两个顶点u,v∈V (G)且d (u)=d (v)时,满足S (u)=S (v),则称f是图G的一个点可约k-全染色,其中S(u)表示顶点u和点u的关联边上分配的颜色组成的色集合。运用图的色集合事先分配法、组合分析法和构造染色法,结合完美匹配探讨了完全三部图Km,n,p的点可约全染色问题,进一步确定了Km,n,p的点可约全色数。

• 单位
  兰州交通大学