稀疏图平方图的染色数上界

作者：张艳

来源：吉林大学学报(理学版), 2020, 58(03): 575-589.

DOI：10.13413/j.cnki.jdxblxb.2019315

• k-顶点染色
• 平方图
• 最大平均度
• 色数

图G的平方G2定义为顶点集V(G)=V(G2),并且uv∈E(G2)当且仅当u和v之间的距离至多为2.G2的色数χ(G2)是指使得G2存在正常k-顶点染色的最小整数k.用权转移的方法证明:如果mad(G)<4且Δ(G)≥7,则χ(G2)≤3Δ(G)+1;如果mad(G)≤4且Δ(G)≥8,则χ(G2)≤3Δ(G)+5.

• 单位
  天津大学