路的半强积与强积的距离染色

摘要

图G的k-距离染色是指G中距离不超过k的顶点分配不同颜色的顶点染色,其中k∈N⁺。G的k-距离色数是指G的k-距离染色所用最少的颜色数,记为χ_k（G）。2个简单图G与H的半强积G·H是具有顶点集V（G）×V（H）的简单图,其中2个顶点（u,v）与（u′,v′）相邻当且仅当uu′∈E（G）且vv′∈E（H）,或u=u′且vv′∈E（H）。2个简单图G与H的强积G■H是具有顶点集V（G）×V（H）的简单图,其中2个顶点（u,v）与（u′,v′）相邻当且仅当uu′∈E（G）且vv′∈E（H）,或u=u′且vv′∈E（H）,或v=v′且uu′∈E（G）。对任意整数k≥2,得到了2个路的半强积与强积的k-距离色数。

关键词

路 / 半强积 / 强积 / 距离染色 / 距离色数