首页|Even Cycle Decompositions of index 3 by a novel coloring technique
Even Cycle Decompositions of index 3 by a novel coloring technique
扫码查看
点击上方二维码区域，可以放大扫码查看
原文链接
NSTL
Elsevier
An even cycle decomposition of an Eulerian graph is a partition of the edge set into even cycles. We color the even cycles so as two cycles sharing at least one vertex receive distinct colors. If k is the minimum number of required colors in such a coloring, then the even cycle decomposition has index k. We prove that the line graph of every bridgeless cubic graph of oddness 2 has an even cycle decomposition of index 3. The same property holds for the line graphs of some infinite families of class 2 cubic graphs with arbitrary large oddness. The construction of even cycle decompositions of index 3 in the line graph of a class 2 cubic graph is alternative to the constructions that are known in the literature; that one for the line graph of a cubic graph with arbitrary large oddness is also a new contribution to the more general problem on the existence of even cycle decompositions in the line graph of a bridgeless cubic graph. The constructions are obtained by applying a novel coloring technique on the edges of the line graph. (c) 2022 Elsevier B.V.
Even cyclesDecompositionsLine graphClass 2 cubic graphs4-REGULAR GRAPHSMINIMUM NUMBER
NSTL
Elsevier
