黄会芸

（南京化工职业技术学院，江苏南京 210048）

一类图的列表强边染色

黄会芸

（南京化工职业技术学院，江苏南京 210048）

给出了列表强边染色的定义，证明了若G为d（x）＋d（y）≤5，则强边选择数Sχ′l（G）≤6.

染色；强边染色；强边色数；列表强边染色；强边选择数

1 基本概念和主要结论

仅考虑有限、无向、无环但可以有平行边的图.用G（V，E）来表示图，其中V表示图G的顶点集，E表示图G的边集.图G的一个k－边正常染色是指一个映射φ：E（G）→｛1，2，…，k｝，若对任何2个相邻的边e和e′，均有φ（e）＝φ（e′），简称为图G的一个k－边染色或称该图是k－边可染的，最小的整数k称为G的边色数，记为χ′（G）.

图G的k－强边染色是正常k－边染色，使得没有相邻于具有相同颜色的2条边.若图G存在k－强边染色，则称图G是k－强边可染的.图G的强边色数是使得G是k－强边可染的最小的整数k，记为sχ′（G）.图G的部分强边着色是指一个满足上述条件的着色，除了G的某些边未被着色.

文献［1］中提出一个公开问题：如果G是二部图，图中的任意一条边xy∈E（G），那么d（x）＋d（y）≤5.文献［2］中证明若d（x）＋d（y）≤5，则sχ′（G）≤6.

给G的每条边e分配一个颜色列表L（e），称G是L－强边染色的是指对每条边e，都可从其对应列表中L（e）找到一种染色f（e）∈L（e），使得f是G的一个强边染色.如果每条边列表长度都相同，此时强边着色数（或强边选择数）定义为满足下面条件的最小的正整数k，使对G的任一边e，只要当｜L（e）｜≥k时，G都是L强边可染的.设L为G的任意一个边列表分配，G的部分L－强边染色是部分强边染色f使得对于任意e∈E⊆E（G），有f（e）∈L（e）.

图1 H0

文献［3］中得到如下结论：当Δ（G）≤3且δ（G）≤2，则）≤10；若G为3正则图，当g（G）＝3时≤10；若G为3正则图，当g（G）≥4时

笔者将证明……