Between proper and strong edge-colorings

2019-09-30
10:00–11:00
FAMNIT-MP1
Borut Lužar (Fakulteta za informacijske študije v Novem mestu)
Between proper and strong edge-colorings

In the talk, we will discuss edge-colorings of (sub)cubic graphs. Namely, we will consider edge-colorings in which we work with two types of colors: the proper and the strong colors. The edges colored with the same proper color form a matching (no two edges are incident), and the edges colored with the same strong color form an induced matching (no two edges are incident to a common edge). Clearly, when all the colors are proper, the edge-coloring of a graph is proper, and if all the colors are required to be strong, we have a strong edge-coloring. The tight upper bounds for the chromatic indices of the above two extremal colorings are long established, thus we will focus to edge-colorings with combinations of proper and strong colors. Such colorings have been investigated before, but only as a tool to obtain results for other types of colorings. Systematically, they have been introduced just recently by Gastineau and Togni as the edge coloring variation of S-packing colorings. We will present results on the topic and give a number of open problems.