论文标题
在适当的和强的边缘图之间
Between proper and strong edge-colorings of subcubic graphs
论文作者
论文摘要
在适当的边缘颜色中，每种颜色的边缘匹配。如果其边缘的最终偏见引起匹配，则会引起匹配。强烈的边缘颜色是一种边缘颜色，其中每种颜色的边缘都具有诱导的匹配。我们考虑中间类型的边缘色，其中允许一些颜色的边缘形成匹配，其余形式引起的匹配。我们的研究是由最近在S填充边缘颜色的Gastineau和Togni的论文中提出的猜想（在立方图的S包装边缘上的边缘颜色上，离散的Appl。Math。259（2019），63-75）声称，通过允许另外三个诱导的匹配，可以节省一个匹配的颜色，从而可以节省一个匹配的颜色。我们证明，每个具有最高度3的图表都可以分解为一个匹配，最多可以将8个引起的匹配和两个匹配和最多的5个匹配。我们还表明，如果图在I类中，则可以减少诱导匹配的数量，从而确认上述I类图形的猜想。
In a proper edge-coloring the edges of every color form a matching. A matching is induced if the end-vertices of its edges induce a matching. A strong edge-coloring is an edge-coloring in which the edges of every color form an induced matching. We consider intermediate types of edge-colorings, where edges of some colors are allowed to form matchings, and the remaining form induced matchings. Our research is motivated by the conjecture proposed in a recent paper of Gastineau and Togni on S-packing edge-colorings (On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019), 63-75) asserting that by allowing three additional induced matchings, one is able to save one matching color. We prove that every graph with maximum degree 3 can be decomposed into one matching and at most 8 induced matchings, and two matchings and at most 5 induced matchings. We also show that if a graph is in class I, the number of induced matchings can be decreased by one, hence confirming the above-mentioned conjecture for class I graphs.
