Geodesic
List Star Edge-Coloring of Subcubic Graphs
Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 1037-1054.

Voir la notice de l'article provenant de la source Library of Science

A star edge-coloring of a graph G is a proper edge coloring such that every 2-colored connected subgraph of G is a path of length at most 3. For a graph G, let the list star chromatic index of G, ch_st^' (G), be the minimum k such that for any k-uniform list assignment L for the set of edges, G has a star edge-coloring from L. Dvořák, Mohar and Šámal asked whether the list star chromatic index of every subcubic graph is at most 7. We prove that it is at most 8. We also prove that if the maximum average degree of a subcubic graph G is less than 73 (respectively, 52), then ch_st^' (G) ≤ 5 (respectively, ch_st^' (G) ≤ 6).
Keywords: graph coloring, edge coloring, star coloring, planar graphs 
@article{DMGT_2018_38_4_a11,
     author = {Kerdjoudj, Samia and Kostochka, Alexandr and Raspaud, Andr\'e},
     title = {List {Star} {Edge-Coloring} of {Subcubic} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1037--1054},
     publisher = {mathdoc},
     volume = {38},
     number = {4},
     year = {2018},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a11/}
}
TY  - JOUR
AU  - Kerdjoudj, Samia
AU  - Kostochka, Alexandr
AU  - Raspaud, André
TI  - List Star Edge-Coloring of Subcubic Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2018
SP  - 1037
EP  - 1054
VL  - 38
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a11/
LA  - en
ID  - DMGT_2018_38_4_a11
ER  - 
%0 Journal Article
%A Kerdjoudj, Samia
%A Kostochka, Alexandr
%A Raspaud, André
%T List Star Edge-Coloring of Subcubic Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2018
%P 1037-1054
%V 38
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a11/
%G en
%F DMGT_2018_38_4_a11
Kerdjoudj, Samia; Kostochka, Alexandr; Raspaud, André. List Star Edge-Coloring of Subcubic Graphs. Discussiones Mathematicae. Graph Theory, Tome 38 (2018) no. 4, pp. 1037-1054. http://geodesic.mathdoc.fr/item/DMGT_2018_38_4_a11/

[1] O.V. Borodin, Criterion of chromaticity of a degree prescription, in: Abstracts of IV All-Union Conf. on Theoretical Cybernetics, Novosibirsk (1977) 127–128, in Russian.

[2] L. Bezegova, B. Lužar, M. Mockovčiaková, R. Soták and R. Škrekovski, Star edge coloring of some classes of graphs, J. Graph Theory 81 (2016) 73–82. doi:10.1002/jgt.21862

[3] K. Deng, X.S. Liu and S.L. Tian, Star edge coloring of trees, J. Shandong Univ. Nat. Sci. 46 (2011) 84–88, in Chinese.

[4] Z. Dvořák, B. Mohar and R. Šámal, Star chromatic index, J. Graph Theory 72 (2013) 313–326. doi:10.1002/jgt.21644

[5] G. Fertin, A. Raspaud and B. Reed, On star coloring of graphs, Lecture Notes in Comput. Sci. 2204 (2001) 140–153. doi:10.1007/3-540-45477-2_14

[6] B. Grünbaum, Acyclic colorings of planar graphs, Israel J. Math. 14 (1973) 390–408. doi:10.1007/BF02764716

[7] H. Hocquard, M. Montassier, A. Raspaud and P. Valicov, On strong-edge coloring of subcubic graphs, Discrete Appl. Math. 161 (2013) 2467–2479. doi:10.1016/j.dam.2013.05.021

[8] A.V. Kostochka, M. Stiebitz and B. Wirth, The colour theorems of Brooks and Gallai extended, Discrete Math. 162 (1996) 299–303. doi:10.1016/0012-365X(95)00294-7

[9] X.S. Liu and K. Deng, An upper bound on the star chromatic index of graphs with δ ≤ 7, J. Lanzhou Univ. (Nat. Sci.) 44 (2008) 94–95.

[10] H. Zhu and Z. Miao, On strong list edge coloring of subcubic graphs, Discrete Math. 333 (2014) 6–13. doi:10.1016/j.disc.2014.06.004