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.

Between proper and strong edge-colorings
Datum / Date: 30.9.19
Čas / Time: 10:00–11:00
Predavalnica / Location: FAMNIT-MP1
Predavatelj / Lecturer: Borut Lužar (Fakulteta za informacijske študije v Novem mestu)
Naslov / Title: Between proper and strong edge-colorings
Povzetek / Abstract: