DĘBSKI, Michał Karol, Kontanty JUNOSZA-SZANIAWSKI and Małgorzata ŚLESZYŃSKA-NOWAK. Strong chromatic index of K-1,t-free graphs. Discrete Applied Mathematics. 2020, vol. 284, No 1, p. 53-60. ISSN 0166-218X. Available from: https://dx.doi.org/10.1016/j.dam.2020.03.024.
Other formats:   BibTeX LaTeX RIS
Basic information
Original name Strong chromatic index of K-1,t-free graphs
Authors DĘBSKI, Michał Karol (616 Poland, belonging to the institution), Kontanty JUNOSZA-SZANIAWSKI and Małgorzata ŚLESZYŃSKA-NOWAK.
Edition Discrete Applied Mathematics, 2020, 0166-218X.
Other information
Original language English
Type of outcome Article in a journal
Field of Study 10201 Computer sciences, information science, bioinformatics
Country of publisher Netherlands
Confidentiality degree is not subject to a state or trade secret
WWW URL
Impact factor Impact factor: 1.139
RIV identification code RIV/00216224:14330/20:00126001
Organization unit Faculty of Informatics
Doi http://dx.doi.org/10.1016/j.dam.2020.03.024
UT WoS 000543418800006
Keywords in English claw-free graphs; strong chromatic index; unit disk graphs
Tags International impact, Reviewed
Changed by Changed by: RNDr. Pavel Šmerk, Ph.D., učo 3880. Changed: 28/3/2023 11:23.
Abstract
A strong edge-coloring of a graph G is a coloring of the edges of G such that each color class is an induced matching. The strong chromatic index of G is the minimum number of colors in a strong edge-coloring of G. We show that the strong chromatic index of a claw-free graph with maximum degree Delta is at most 1.125 Delta(2) + Delta, which confirms the conjecture of Erdos and Negetfil from 1985 for this class of graphs for Delta >= 12. We also prove an upper bound of (2 - 1/t-2 ) Delta(2) on strong chromatic index of K-1,K-t-free graphs with maximum degree Delta for all t >= 4 and give an improved result 1.625 Delta(2) for unit disk graphs.
PrintDisplayed: 10/10/2024 18:33