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

DOI10.37236/9202zbMATH Open1457.05022arXiv1805.09586OpenAlexW3118500630MaRDI QIDQ2223458FDOQ2223458

Authors: Behnaz Omoomi, Elham Roshanbin, Marzieh Vahid Dastjerdi 

Publication date: 29 January 2021

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

Abstract: 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.

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

File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

Recommendations

• Star Chromatic Index
• A survey on star edge-coloring of graphs
• Star coloring of graphs
• scientific article; zbMATH DE number 2044931
• A note on a conjecture of star chromatic index for outerplanar graphs
• On star coloring of splitting graphs.
• Star edge-colorings of plane graphs with cycle conditions
• On star edge colorings of bipartite and subcubic graphs
• Star edge coloring of graphs with \(\mathrm{Mad}(G)<\frac{14}{5}\)
• On structural parameterizations of star coloring

zbMATH Keywords

treecomplexitypolynomial algorithmcaterpillarstar vertex coloring

Mathematics Subject Classification ID

Trees (05C05) Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Coloring of graphs and hypergraphs (05C15)

Cites Work

• Graph theory
• Star coloring of graphs
• A remark on the existence of finite graphs
• Estimation of Sparse Jacobian Matrices and Graph Coloring Blems
• Star chromatic index of subcubic graphs
• Star edge coloring of some classes of graphs
• Star Chromatic Index
• Star 5-edge-colorings of subcubic multigraphs
• A simple Havel-Hakimi type algorithm to realize graphical degree sequences of directed graphs
• On a star chromatic index of subcubic graphs
• List star chromatic index of sparse graphs
• An upper bound on the star chromatic index of graphs with \(\varDelta\geqslant 7\)

Cited In (5)

• Acyclic, star, and injective colouring: bounding the diameter
• On structural parameterizations of star coloring
• Skew chromatic index of 2-rooted sibling trees and cyclic snake graphs
• List star edge-coloring of claw-free subcubic multigraphs
• The complexity of star colouring in bounded degree graphs and regular graphs

This page was built for publication: A polynomial time algorithm to find the star chromatic index of trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2223458)