A matching $M$ in a graph $G$ is {\em semistrong} if every edge of $M$ has an endvertex of degree one in the subgraph induced by the vertices of $M$. A {\em semistrong edge-coloring} of a graph $G$ is a proper edge-coloring in which every color class induces a semistrong matching. In this paper, we continue investigation of properties of semistrong edge-colorings initiated by Gy\'{a}rf\'{a}s and Hubenko ({Semistrong edge coloring of graphs}. \newblock {\em J. Graph Theory}, 49 (2005), 39--47). We establish tight upper bounds for general graphs and for graphs with maximum degree $3$. We also present bounds about semistrong edge-coloring which follow from results regarding other, at first sight non-related, problems. We conclude the paper with several open problems.
翻译：图表中匹配的$M$是 $G$ 的半坚硬 。 如果每个美元的边缘都有一个由 $M$ 的顶端顶端, 由 $M$ 的顶端是 $G$ 的顶端。 $G$ 的 $M$ 是一个适当的边色, 每个彩色等级都引来半坚色。 在本文中, 我们继续调查由 Gy\ { a}rf\ {a} 和 Hubenko ( 图表的超强边缘色 ) 所引发的半坚硬色的属性 。\ newblock ~em J. Grap Theory}, 49 (2005) 39- 47 。 我们为普通图形和最大值为 $3 的图形设定了紧紧的上方界限 。 我们还展示了半坚色的边端的界限, 这些界限来自其他初看起来无关的问题的结果 。 我们用几个开放的问题来完成此纸张 。
相关内容
微信扫码咨询专知VIP会员