Name
Abstract | ||
|---|---|---|
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. |
Year | Venue | Field |
|---|---|---|
2018 | Electr. J. Comb. | Graph theory,Discharging method,Discrete mathematics,Edge coloring,Odd graph,Combinatorics,Graph power,Bound graph,Degree (graph theory),Mathematics,Planar graph |
DocType | Volume | Issue |
Journal | 25 | 3 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
10 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| philip deorsey | 1 | 0 | 0.34 |
| Jennifer Diemunsch | 2 | 4 | 2.85 |
| Michael Ferrara | 3 | 31 | 10.52 |
| nathan graber | 4 | 0 | 0.68 |
| Stephen G. Hartke | 5 | 159 | 24.56 |
| Sogol Jahanbekam | 6 | 15 | 3.36 |
| Bernard Lidický | 7 | 9 | 5.00 |
| luke l nelsen | 8 | 0 | 0.68 |
| Derrick Stolee | 9 | 34 | 9.37 |
| eric sullivan | 10 | 0 | 0.34 |