Star multigraphs with three vertices of maximum degree
Star multigraphs with three vertices of maximum degree
复制标题
DOI：
10.1017/s030500410006610x
复制
发表时间：
1986-09
影响因子：
0.8
通讯作者：
A. Chetwynd;A. Hilton
中科院分区：
文献类型：
--
作者：
A. Chetwynd;A. Hilton
我们在这里考虑的图要么是简单图，也就是说，它们没有环或多条边，要么是多图，也就是说，它们可能有多条边连接一对顶点，但同样没有环。特别地，我们将考虑一种特殊的多重图，称为星形多重图：这是一个包含顶点v* 的多重图，称为星形中心，它与每个非简单边关联。重图G的一个边染色是一个映射E（G）→，其中是一个颜色集，E（G）是G的边集，使得没有两个接受相同颜色的边有公共顶点。图G的色指数或边色数χ′（G）是图G的边色数χ′（G）的最小值，||其中，G的边着色存在。推广了Vizing [14]的一个著名定理，我们在[6]中证明了：对于一个星重图G，其中Δ（G）表示G的最大度（即与一个顶点关联的边的最大数目）。当χ′（G）= Δ（G）时，称星重图为第1类，否则称其为第2类。
The graphs we consider here are either simple graphs, that is they have no loops or multiple edges, or are multigraphs, that is they may have more than one edge joining a pair of vertices, but again have no loops. In particular we shall consider a special kind of multigraph, called a star-multigraph: this is a multigraph which contains a vertex v*, called the star-centre, which is incident with each non-simple edge. An edge-colouring of a multigraph G is a map ø: E(G)→, where is a set of colours and E(G) is the set of edges of G, such that no two edges receiving the same colour have a vertex in common. The chromatic index, or edge-chromatic numberχ′(G) of G is the least value of || for which an edge-colouring of G exists. Generalizing a well-known theorem of Vizing [14], we showed in [6] that, for a star-multigraph G, where Δ(G) denotes the maximum degree (that is, the maximum number of edges incident with a vertex) of G. Star-multigraphs for which χ′(G) = Δ(G) are said to be Class 1, and otherwise they are Class 2.