On the strong chromatic index of sparse graphs
| Autor: | Bernard Lidicky, Philip DeOrsey, Michael Ferrara, Jennifer Diemunsch, Stephen G. Hartke, Luke L. Nelsen, Sogol Jahanbekam, Derrick Stolee, Nathan Graber, Eric Sullivan |
|---|---|
| Předmět: |
Discharging method
0102 computer and information sciences 01 natural sciences Upper and lower bounds Theoretical Computer Science Combinatorics symbols.namesake Graph power FOS: Mathematics Mathematics - Combinatorics Discrete Mathematics and Combinatorics 0101 mathematics Mathematics Discrete mathematics Applied Mathematics 010102 general mathematics Graph theory Planar graph Edge coloring 05C15 Computational Theory and Mathematics 010201 computation theory & mathematics symbols Odd graph Bound graph Combinatorics (math.CO) Geometry and Topology |
| Zdroj: | Scopus-Elsevier |
| Popis: | 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 |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|