关于图的瑕边着色

On Flaw Colourings of Graphs

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

A(λ,β)-flaw k-edge colouring of a connected graph G=(V,E) is a mapping from E to {1,2,…,k} if there is a smallest integer β≥1 such that for every colour j∈{1,2,…,β} there is at least a vertex uj∈V(G)that is incident with λ edges coloured by colour j,and for each color l∈{β+1,…,k} no two edges incident with any vertex v∈V(G)receive the colour l.The(λ,β)-flaw chromatic index of G,denoted by χ(λ,β()G),is the smallest number such that G admits a(λ,β)-flaw k-edge colouring for each k≥χ(λ,β()G).We deduce χ(λ,1)(G...