- 'Philip DeOrsey$^{1,6}$'
- 'Jennifer Diemunsch$^{2,6}$'
- 'Michael Ferrara$^{2,6,7}$'
- 'Nathan Graber$^{2,6}$'
- 'Stephen G. Hartke$^{3,6,8}$'
- 'Sogol Jahanbekam$^{2,6}$'
- 'Bernard Lidický$^{4,6,9}$'
- 'Luke Nelsen$^{2,6}$'
- 'Derrick Stolee$^{4,5,6}$'
- 'Eric Sullivan$^{2,6}$'
title: On the Strong Chromatic Index of Sparse Graphs
---

Introduction
============

A [*proper edge-coloring*]{} of a graph $G$ is an assignment of colors to the edges so that incident edges receive distinct colors. A [*strong edge-coloring*]{} of a graph $G$ is an assignment of colors to the edges so that edges at distance at most two receive distinct colors. A proper edge-coloring is a decomposition of $G$ into matchings, while a strong edge-coloring is a decomposition of $G$ into *induced* matchings. Fouquet and Jolivet [@Fouquet83; @Fouquet84] defined the [*strong chromatic index*]{} of a graph $G$, denoted ${\chi_{s}'(G)}$, as the minimum integer $k$ such that $G$ has a strong edge-coloring using $k$ colors. Erdős and Nešetřil gave the following conjecture, which is still open, and provided an example to show that it would be sharp, if true.

\[Erdos\] For every graph $G$, $\chi'_s(G) \leq \dfrac{5}{4}\Delta(G)^2$ when $\Delta(G)$ is even, and $\chi'_s(G) \leq \dfrac{1}{4}(5\Delta(G)^2-2\Delta(G)+1)$ when $\Delta(G)$ is odd.

Towards this conjecture, Molloy and Reed [@MR] bounded ${\chi_{s}'(G)}$ away from the 