Geodesic
A polynomial time algorithm to find the star chromatic index of trees
Behnaz Omoomi1 ; Elham Roshanbin2 ; Marzieh Vahid Dastjerdi1
1Isfahan University of Technology
2Alzzahra University
The electronic journal of combinatorics, Tome 28 (2021) no. 1
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A star edge coloring of a graph $G$ is a proper edge coloring of $G$ such that every path and cycle of length four in $G$ uses at least three different colors. The star chromatic index of a graph $G$ is the smallest integer $k$ for which $G$ admits a star edge coloring with $k$ colors. In this paper, we present a polynomial time algorithm that finds an optimum star edge coloring for every tree. We also provide some tight bounds on the star chromatic index of trees with diameter at most four, and using these bounds we find a formula for the star chromatic index of certain families of trees.
DOI : 10.37236/9202
Classification : 05C05, 05C15, 68Q25, 05C85
Mots-clés : star vertex coloring, polynomial algorithm, complexity, tree, caterpillar

Behnaz Omoomi  1   ; Elham Roshanbin  2   ; Marzieh Vahid Dastjerdi  1

1 Isfahan University of Technology
2 Alzzahra University 
@article{10_37236_9202,
     author = {Behnaz Omoomi and Elham Roshanbin and Marzieh Vahid Dastjerdi},
     title = {A polynomial time algorithm to find the star chromatic index of trees},
     journal = {The electronic journal of combinatorics},
     year = {2021},
     volume = {28},
     number = {1},
     doi = {10.37236/9202},
     zbl = {1457.05022},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9202/}
}
TY  - JOUR
AU  - Behnaz Omoomi
AU  - Elham Roshanbin
AU  - Marzieh Vahid Dastjerdi
TI  - A polynomial time algorithm to find the star chromatic index of trees
JO  - The electronic journal of combinatorics
PY  - 2021
VL  - 28
IS  - 1
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9202/
DO  - 10.37236/9202
ID  - 10_37236_9202
ER  - 
%0 Journal Article
%A Behnaz Omoomi
%A Elham Roshanbin
%A Marzieh Vahid Dastjerdi
%T A polynomial time algorithm to find the star chromatic index of trees
%J The electronic journal of combinatorics
%D 2021
%V 28
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/9202/
%R 10.37236/9202
%F 10_37236_9202
Behnaz Omoomi; Elham Roshanbin; Marzieh Vahid Dastjerdi. A polynomial time algorithm to find the star chromatic index of trees. The electronic journal of combinatorics, Tome 28 (2021) no. 1. doi: 10.37236/9202

Cité par Sources :