A polynomial time algorithm to find the star chromatic index of trees

DOI10.37236/9202zbMath1457.05022arXiv1805.09586MaRDI QIDQ2223458

Marzieh Vahid Dastjerdi, Behnaz Omoomi, Elham Roshanbin

Publication date: 29 January 2021

Published in: The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1805.09586

zbMATH Keywords

tree; complexity; polynomial algorithm; caterpillar; star vertex coloring

Mathematics Subject Classification ID

68Q25: Analysis of algorithms and problem complexity

05C05: Trees

05C15: Coloring of graphs and hypergraphs

05C85: Graph algorithms (graph-theoretic aspects)

Related Items

Acyclic, star, and injective colouring: bounding the diameter, The complexity of star colouring in bounded degree graphs and regular graphs, On structural parameterizations of star coloring, List star edge-coloring of claw-free subcubic multigraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Star chromatic index of subcubic graphs
• A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
• On a star chromatic index of subcubic graphs
• Star 5-edge-colorings of subcubic multigraphs
• List star chromatic index of sparse graphs
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Star coloring of graphs
• A remark on the existence of finite graphs
• Star Edge Coloring of Some Classes of Graphs
• Star Chromatic Index