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
@article{1860120, author = {Dębski, Michał Karol and JunoszaandSzaniawski, Kontanty and ŚleszyńskaandNowak, Małgorzata}, article_number = {1}, doi = {http://dx.doi.org/10.1016/j.dam.2020.03.024}, keywords = {claw-free graphs; strong chromatic index; unit disk graphs}, language = {eng}, issn = {0166-218X}, journal = {Discrete Applied Mathematics}, title = {Strong chromatic index of K-1,t-free graphs}, url = {https://doi.org/10.1016/j.dam.2020.03.024}, volume = {284}, year = {2020} }
TY - JOUR ID - 1860120 AU - Dębski, Michał Karol - Junosza-Szaniawski, Kontanty - Śleszyńska-Nowak, Małgorzata PY - 2020 TI - Strong chromatic index of K-1,t-free graphs JF - Discrete Applied Mathematics VL - 284 IS - 1 SP - 53-60 EP - 53-60 SN - 0166218X KW - claw-free graphs KW - strong chromatic index KW - unit disk graphs UR - https://doi.org/10.1016/j.dam.2020.03.024 N2 - 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. ER -
DĘBSKI, Michał Karol, Kontanty JUNOSZA-SZANIAWSKI and Małgorzata $\backslash$'SLESZY$\backslash$'NSKA-NOWAK. Strong chromatic index of K-1,t-free graphs. \textit{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.
|