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

DOI10.37236/9202MaRDI QIDQ2223458zbMATH OpenOpenAlexFDO

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)

Copyright license Creative Commons Attribution 4.0 International

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

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

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)

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.

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

Cites work

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

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)