稀疏图的(0,1)-松弛强边着色

作者：刘存肃

来源：南开大学学报(自然科学版), 2020, 53(02): 14-21.

• (s,t)-松弛强k边着色
• (s,t)-松弛强边着色数
• 平面图
• 最大平均度
• 围长

给定一个图G=(V (G),E (G)),图G的(s,t)-松弛强边着色数是指使得图G有(s,t)-松弛强k边着色的最小k值,记作χ′((s,t))(G).证明了在图G中,如果mad (G)<3,Δ≤7,那么χ′((0,1))(G)≤3Δ-1;同时证明了对于任意一个平面图G,如果g (G)≥7,Δ≥4,那么χ′((0,1))(G)≤■

• 单位
  天津大学