不含K_1,3⁺图的强边染色

摘要

一个图G的强边染色是将颜色分配给所有的边，使得每个颜色类的导出子图是一个匹配。在图G的强边染色中所需的最小颜色数称为图G的强边色数，边e=uv的度记为d（e）=d（u）+d（v）,图G的边度记为d（G）=min{d（e）|e∈E（G）}。证明最大度为Δ且图的边度大于顶点数的不含K_1,3⁺图的强边色数至多是Δ²-Δ+1。

关键词

强边染色 / 强边色数 / 边度