关于图的瑕边着色

摘要

图G=(V,E)的一个(λ,β)-瑕k-边着色是一个从E到{1,2,…,k}的映射,且存在一个最小整数β≥1,对每一个色j∈ {1,2,…,β},至少存在一个顶点uj∈V(G)使得顶点uj关联着有色的j条边;对每一个色l∈{β+1,…,k},没有两条相邻边着有色l.图G的(λ,β)-瑕色数被表示为x(λ,β)(G),它是一个最小的整数,使对整数k≥x(λ,β)(G),图G总有一个(λ,β)-瑕k-边着色.在这篇文章中,我们证得x(λ,1)(G)+λ-1≤x'(G)≤x(λ,1)(G)+,其中x'(G)是G的正常边色数,并确定了几个特殊图类的瑕色数.