论文部分内容阅读
图的邻强边染色问题在计算机，网络等领域都有广泛的应用.本学位论文讨论的是图的邻强边染色.用xas(G)表示图的邻强边色数.关于图的邻强边染色，张忠辅等人提出猜测：对于｜V(G)｜≥3的简单连通图G，且G≠C5，则xas(G)≤△(G)+2.但是目前只知道一些特殊图如树，圈，完全二部图，完全图，Halin图，唯圈图等等的邻强边色数及一些上界.
在第二章中我们考虑了一般Mycielski图的邻边强染色的问题.给出具体的5-邻强边染色来证明了圈的一般Mycielski图的邻强边色数为5；还证明了若连通图G(V,E)满足xas(G)≤△(G)+2，则xas(Mn(G))≤△(Mn(G))+2.在第三章中利用最大度为4，围长大于6的平面图的全色数为5的这个性质，证明了最大度为4且围长至少为8的连通平面图G(V,E)满足猜想.研究了最大度为4的图的邻强边染色的问题得到了最大度为4的连通图G(V,E)，有xas(G)≤8.
在第四章中我们利用引理：若图G满足性质，对任意δ(G)≤d≤△(G)，k≥△(G)+1，有d(k-d)≥nd-2，则G有一个k-半点可区别边染色，证明了最小度为δ(G)≥2—n+1且n△≤2—n-1的图G满足猜想.还讨论了一般图的邻强边染色的问题，得到了最大度△≥3的连通图G(V，E)，有xas(G)≤3△(G)-1.