最大度为4的图的关联着色数  

Incidence Coloring of Graphs G with Δ(G)≤4*

作　　者：李珍珍 刘晓平 

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐 [2]新疆工程学院,新疆乌鲁木齐

出　　处：《应用数学进展》2018年第4期334-337,共4页Advances in Applied Mathematics

摘　　要：图中的关联是由图G中的顶点v和图G中与v关联的边e所构成的有序对(v,e),两个关联对(v,e)和(u,f)相邻当且仅当u = v或e = f或uv∈{e,f}成立。图的关联着色是指对图中G的关联有序对进行着色,使得相邻关联对着不同的颜色。图G的关联色数χi(G),是指图G的所有关联着色方式中使用的最小颜色的个数。近期,Gregor,luzar和Sotak证明对于Δ≤4的图G,χi(G)≤7。本文主要目标是对于这一结果给以短的证明。An incidence in a graph G is a pair (v,e), where v is a vertex of G and e is an edge of G incidence to v. Two incidence (v,e) and (u,f) are a djacent if at least one of the following holds: u = v, or e = f or uv∈{e,f}. An incidence coloring of G is a coloring of its incidence assigning distinct colors to adjacent incidences. The incidence chromatic number of G, denoted by χi(G), is the smallest number of colors used in a incidence coloring of G. Recently, Gregor, luzar, and Sotak showed that χi(G)≤7 for a graph G with maximum degree at most 4. The aim of the present paper is to present a short proof of this result.

关 键 词：关联着色 关联着色数 

分 类 号：O1[理学—数学]