About: 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 some of the colors are allowed to form matchings, and the remaining form induced matchings. Our research is motivated by the conjecture proposed in a recent paper on S-packing edge-colorings (N. Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019)). 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 conjecture for this class of graphs.   Goto Sponge  NotDistinct  Permalink

An Entity of Type : fabio:Abstract, within Data Space : wasabi.inria.fr associated with source document(s)

AttributesValues
type
value
  • 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 some of the colors are allowed to form matchings, and the remaining form induced matchings. Our research is motivated by the conjecture proposed in a recent paper on S-packing edge-colorings (N. Gastineau and O. Togni, On S-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019)). 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 conjecture for this class of graphs.
Subject
  • Matching
  • Graph theory
  • Computational problems in graph theory
  • Polynomial-time problems
  • Combinatorial optimization
part of
is abstract of
is hasSource of
Faceted Search & Find service v1.13.91 as of Mar 24 2020


Alternative Linked Data Documents: Sponger | ODE     Content Formats:       RDF       ODATA       Microdata      About   
This material is Open Knowledge   W3C Semantic Web Technology [RDF Data]
OpenLink Virtuoso version 07.20.3229 as of Jul 10 2020, on Linux (x86_64-pc-linux-gnu), Single-Server Edition (94 GB total memory)
Data on this page belongs to its respective rights holders.
Virtuoso Faceted Browser Copyright © 2009-2024 OpenLink Software