Geodesic
On the strong chromatic index of sparse graphs
Philip DeOrsey1 ; Michael Ferrara2 ; Nathan Graber2 ; Stephen G. Hartke2 ; Luke L. Nelsen2 ; Eric Sullivan2 ; Sogol Jahanbekam3 ; Bernard Lidický4 ; Derrick Stolee5 ; Jennifer White6
1Westfield State University
2University of Colorado Denver
3Rochester Institute of Technology
4Iowa State University
5Microsoft
6Saint Vincent College
The electronic journal of combinatorics, Tome 25 (2018) no. 3
Full Text
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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 ${\rm 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 ${\rm 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 ${\rm girth}(G) \geq 28$, then $\chi'_s(G)N \leq 7$, improving a more general bound of Wang and Zhao from [Odd graphs and its applications to the strong edge coloring, Applied Mathematics and Computation, 325 (2018), 246-251] in this case.
DOI : 10.37236/5390
Classification : 05C15, 05C42
Mots-clés : strong edge coloring, strong chromatic index, sparse graphs

Philip DeOrsey  1   ; Michael Ferrara  2   ; Nathan Graber  2   ; Stephen G. Hartke  2   ; Luke L. Nelsen  2   ; Eric Sullivan  2   ; Sogol Jahanbekam  3   ; Bernard Lidický  4   ; Derrick Stolee  5   ; Jennifer White  6

1 Westfield State University
2 University of Colorado Denver
3 Rochester Institute of Technology
4 Iowa State University
5 Microsoft
6 Saint Vincent College 
@article{10_37236_5390,
     author = {Philip DeOrsey and Michael Ferrara and Nathan Graber and Stephen G. Hartke and Luke L. Nelsen and Eric Sullivan and Sogol Jahanbekam and Bernard Lidick\'y and Derrick Stolee and Jennifer White},
     title = {On the strong chromatic index of sparse graphs},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {3},
     doi = {10.37236/5390},
     zbl = {1393.05112},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/5390/}
}
TY  - JOUR
AU  - Philip DeOrsey
AU  - Michael Ferrara
AU  - Nathan Graber
AU  - Stephen G. Hartke
AU  - Luke L. Nelsen
AU  - Eric Sullivan
AU  - Sogol Jahanbekam
AU  - Bernard Lidický
AU  - Derrick Stolee
AU  - Jennifer White
TI  - On the strong chromatic index of sparse graphs
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/5390/
DO  - 10.37236/5390
ID  - 10_37236_5390
ER  - 
%0 Journal Article
%A Philip DeOrsey
%A Michael Ferrara
%A Nathan Graber
%A Stephen G. Hartke
%A Luke L. Nelsen
%A Eric Sullivan
%A Sogol Jahanbekam
%A Bernard Lidický
%A Derrick Stolee
%A Jennifer White
%T On the strong chromatic index of sparse graphs
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/5390/
%R 10.37236/5390
%F 10_37236_5390
Philip DeOrsey; Michael Ferrara; Nathan Graber; Stephen G. Hartke; Luke L. Nelsen; Eric Sullivan; Sogol Jahanbekam; Bernard Lidický; Derrick Stolee; Jennifer White. On the strong chromatic index of sparse graphs. The electronic journal of combinatorics, Tome 25 (2018) no. 3. doi: 10.37236/5390

Cité par Sources :