| 摘要: |
| 著名图论专家Erds和Neetǐil对图的强边色数上界提出了一个猜想：当最大度Δ为偶数时，〖WTBX〗χ′s(G)≤〖SX(〗5〖〗4〖SX)〗Δ2；当最大度Δ为奇数时，χ′s(G)≤〖SX(〗1〖〗4〖SX)〗(5Δ2－2Δ+1)；并且给出了当Δ=4时的最优图.此处构造了一族图，并证明了当最大度为奇数时，如果Erds和Neetǐil提出的强边着色猜想成立，则猜想中的上界是最优的. |
| 关键词: 边着色 强边着色 最优图 |
| DOI： |
| 分类号: |
| 基金项目: |
|
| The Optimum Graph of Strong Edge Coloring Conjecture |
|
ZHANG Wei biao
|
| Abstract: |
| The famous graph theory expert Erds and Neetǐil conjectured that strong edge coloring number of a graph is bounded above by 〖SX(〗5〖〗4〖SX)〗Δ2 when Δ is even and 〖SX(〗1〖〗4〖SX)〗(5Δ2－2Δ+1) when Δ is odd. They gave a graph of Δ=4. In this paper, we construct a series of such graphs, and prove that if the Strong Edge Coloring Conjecture is correct, the boundary number is optimum when Δ is odd. |
| Key words: edge coloring strong edge coloring the optimal graph |
