Parsimonious edge coloring
Parsimonious edge coloring
复制标题
DOI：
10.1016/0012-365x(94)00254-g
复制
发表时间：
1996-01-15
影响因子：
0.8
通讯作者：
Haas, R
中科院分区：
文献类型：
--
作者：
Albertson, MO;Haas, R
在最大度为Delta的图G中，设gamma表示可以为Delta边着色的边的最大比例。本文研究了伽玛的下界以及伽玛离1有界的无限族图。例如，如果G是三次幂，则大于等于13/25；存在无穷一族的3连通三次图其中小于等于25/27。
In a graph G of maximum degree Delta, let gamma denote the largest fraction of edges that can be a Delta-edge-colored. This paper investigates lower bounds for gamma together with infinite families of graphs in which gamma is bounded away from 1. For instance, if G is cubic, then gamma greater than or equal to 13/25; and there exists an infinite family of 3-connected cubic graphs in which gamma less than or equal to 25/27.