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

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

摘要: 图中的关联是由图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。本文主要目标是对于这一结果给以短的证明。

Abstract: 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.