Between proper and strong edge‐colorings of subcubic graphs
Hervé Hocquard, Dimitri Lajou, Borut Lužar
Abstract
Abstract 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 ‐packing edge‐colorings asserting that, for subcubic graphs, 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 eight induced matchings, and two matchings and at most five 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.