On the strong chromatic index of sparse graphs (Q1658764): Difference between revisions

Summary: The strong chromatic index of a graph \(G\), denoted \(\chi^\prime_s(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^\prime_{s,\ell}(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) \geqslant 41\) then \(\chi^\prime_{\ell,s}(G)\leqslant 5\), answering a question of \textit{O. V. Borodin} and \textit{A. O. Ivanova} [Discuss. Math., Graph Theory 33, No. 4, 759--770 (2013; Zbl 1301.05118)]. We further show that if \(G\) is a subcubic planar graph and \(\mathrm{girth}(G) \geqslant 30\), then \(\chi^\prime_s(G)\leqslant 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) \geqslant 28\), then \(\chi'_s\leqslant 7\), improving a more general bound of \textit{T. Wang} and \textit{X. Zhao} from [``Odd graphs and its application on the strong edge-coloring'', Appl. Math. Comput. 325, 246--251 (2018)].