图的字典积的点可约边染色

摘要

设f:E（G）→{1,2,…,k}是图G的一个（非正常）边染色，其中1≤k≤Δ,若对任意2个顶点u,v∈V（G）且d（u）=d（v）时，满足C（u）=C（v）,则称f是图G的一个点可约k-边染色，其中C（u）表示点u关联边上分配的颜色组成的色集合。将最大的正整数k称为图G的点可约边色数。根据字典积图的结构特点，运用组合分析法给出了简单图G和H的字典积G[H]的点可约边色数的一个下界。作为应用，得到了图■和P_n[H]的点可约边色数。

关键词

字典积 / 点可约边染色 / 点可约边色数