Seminár z teórie grafov - Roman Soták (30.4.2026)
vo štvrtok 30.4.2026 o 9:50 hod. v miestnosti M 213
Prednášajúci: Roman Soták (UPJŠ Košice)
Názov prednášky: List strong edge-colouring of graphs with small maximum degree
Termín: 30.4.2026, 9:50 hod., M 213
Abstrakt:
Astrong edge-coloring of a graph is an edge-coloring in which every color class is an induced matching. The least number of colors needed for a strong edge-coloring of a graph is the strong chromatic index.
We consider the list version of the coloring and prove that the list strong chromatic index of graphs with maximum degree 3 is at most 10. This bound is tight and improves the previous bound of 11 colors ([1]).
Next, we consider graphs with maximum degree 4, where the best known bound for the list strong edge-coloring is 22 ([2]). We improve this result and establish an upper bound of 21 for the strong list chromatic index of subquartic graphs. Since there exist subquartic graphs whose strong chromatic index is 20, our bound is only one above the best possible.
(joint work with B. Lužar, E. Máčajová, D. Švecová)
References
[1] T. Dai, G. Wang, D. Yang, and G. Yu, Strong list-chromatic index of subcubic graphs, Discrete Math., 341(12) (2018), 3434–3440.
[2] B. Zhang,Y. Chang, J. Hu, M. Ma, D. Yang, List strong edge coloring of graphs with maximum degree 4. Discrete Math. 343(6), 111854 (2020)