On the Strong Chromatic Index of Sparse Graphs

Abstract

The strong chromatic index of a graph $G$, denoted ${\chi }_s^{\prime }(G)$, is the least number of colors needed to edge-color $G$ so that edges at distance at most two receive distinct colors. The strong list chromatic index, denoted ${\chi }_{s,\ell }^{\prime }(G)$, is the least integer $k$ such that if arbitrary lists of size $k$ are assigned to each edge then $G$ can be edge-colored from those lists where edges at distance at most two receive distinct colors. We use the discharging method, the Combinatorial Nullstellensatz, and computation to show that if $G$ is a subcubic planar graph with $\mathrm{girth}(G)\ge 41$ then ${\chi }_{s,\ell }^{\prime }(G)\le 5$, answering a question of Borodin and Ivanova [Precise upper bound for the strong edge chromatic number of sparse planar graphs, Discuss. Math. Graph Theory, 33(4), (2014) 759--770]. We further show that if $G$ is a subcubic planar graph and $\mathrm{girth}(G)\ge 30$, then ${\chi }_s^{\prime }(G)\le 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $\mathrm{girth}(G)\ge 28$, then ${\chi }_s^{\prime }(G)\le 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its application on the strong edge coloring, arXiv:1412.8358] in this case.

15 pages, 10 figures

Cited by in corpus (1)

• Strong edge colorings of graphs and the covers of Kneser graphs