2021-01-14 Borut Lužar - From proper to strong edge-colorings of subcubic graphs скачать в хорошем качестве

2021-01-14 Borut Lužar - From proper to strong edge-colorings of subcubic graphs

Speaker: Borut Lužar Title: From proper to strong edge-colorings of subcubic graphs 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 an edge-coloring variation of $S$-packing colorings~\cite{GasTog19}. We will present results on the topic and give a number of open problems. Joint work with Herve Hocquard and Dimitri Lajou. \bibitem{GasTog19} N. Gastineau, O. Togni, On $S$-packing edge-colorings of cubic graphs, Discrete Appl. Math. 259 (2019), 63--75. \bibitem{HerLajLuz21} H. Hocquard, D. Lajou, B. Lu\v{z}ar, Between proper and strong edge-colorings of subcubic graphs, \href{https://arxiv.org/abs/2011.02175}{arXiv preprint 2011.02175}, 2020.