تقرير
On the Strong Chromatic Index of Sparse Graphs
| العنوان: | On the Strong Chromatic Index of Sparse Graphs |
|---|---|
| المؤلفون: | DeOrsey, Philip, Diemunsch, Jennifer, Ferrara, Michael, Graber, Nathan, Hartke, Stephen G., Jahanbekam, Sogol, Lidicky, Bernard, Nelsen, Luke L., Stolee, Derrick, Sullivan, Eric |
| سنة النشر: | 2015 |
| المجموعة: | Mathematics |
| مصطلحات موضوعية: | Mathematics - Combinatorics, 05C15 |
| الوصف: | The strong chromatic index of a graph $G$, denoted $\chi_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_{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 $\operatorname{girth}(G) \geq 41$ then $\chi_{s,\ell}'(G) \leq 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 $\operatorname{girth}(G) \geq 30$, then $\chi_s'(G) \leq 5$, improving a bound from the same paper. Finally, if $G$ is a planar graph with maximum degree at most four and $\operatorname{girth}(G) \geq 28$, then $\chi_s'(G) \leq 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. Comment: 15 pages, 10 figures |
| نوع الوثيقة: | Working Paper |
| DOI: | 10.37236/5390 |
| URL الوصول: | http://arxiv.org/abs/1508.03515 |
| رقم الأكسشن: | edsarx.1508.03515 |
| قاعدة البيانات: | arXiv |
| DOI: | 10.37236/5390 |
|---|