稀疏图平方图的染色数上界
来源：吉林大学学报·理学版杂志2020年第3期北京时间：
作者：张艳
单位：天津大学 应用数学中心, 天津 300072
摘要：图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.
关键词：k顶点染色,平方图,最大平均度,色数
