We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Between proper and strong edge‐colorings of subcubic graphs.
- Authors
Hocquard, Herve; Lajou, Dimitri; Lužar, Borut
- 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 S $S$‐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.
- Subjects
LOGICAL prediction; COLORS; COLOR; CHARTS, diagrams, etc.; MOTIVATION (Psychology)
- Publication
Journal of Graph Theory, 2022, Vol 101, Issue 4, p686
- ISSN
0364-9024
- Publication type
Article
- DOI
10.1002/jgt.22848