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:

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.

Share with others

Accessibility Toolbar

Privacy Overview

This website uses cookies so that we can provide you with the best user experience possible. Cookie information is stored in your browser and performs functions such as recognising you when you return to our website and helping our team to understand which sections of the website you find most interesting and useful.