Seminar of Graph Theory - Andre Raspaud (3.10.2024)
Thursday 3.10.2024 at 9:50, Lecture room M 213
Andre Raspaud (LABRI, Bordeaux University, France):
Induced 2-improper edge coloring
Abstract:
A strong edge coloring of a graph is a decomposition of its edge set into induced disjoint matchings. An injective edge coloring (or induced star arboricity) is a decomposition of its edge set into induced disjoint stars. In this talk we present a new edge coloring: the induced 2-improper edge coloring (i2i-edge coloring for short) of a graph G is a decomposition of its edge set into disjoint edge sets of induced subgraphs of maximum degree 2. We define the corresponding chromatic index. We present the relationship between this new notion and the edge colorings already defined. We give bounds for the i2i-chromatic index of complete graphs and graphs with constraints on the degree.