Star Chromatic Index

DOI10.1002/JGT.21644zbMATH Open1262.05049OpenAlexW2154102540MaRDI QIDQ4916092FDOQ4916092

Authors Zdeněk Dvořák, Bojan Mohar, Robert Šámal

Publication date 19 April 2013

Published in Journal of Graph Theory (Search for Journal in Brave)

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

zbMATH Keywords

graph coloringedge coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The star chromatic index $ch{i_s}^{\prime }(G)$ of a graph $G$ is the minimum number of colors needed to properly color the edges of the graph so that no path or cycle of length four is bi-colored. We obtain a near-linear upper bound in terms of the maximum degree $Delta=Delta(G)$. Our best lower bound on $ch{i_s}^{\prime }$ in terms of $Delta$ is $2Delta(1+o(1))$ valid for complete graphs. We also consider the special case of cubic graphs, for which we show that the star chromatic index lies between 4 and 7 and characterize the graphs attaining the lower bound. The proofs involve a variety of notions from other branches of mathematics and may therefore be of certain independent interest.

Recommendations

• Star chromatic number
• Star chromatic bounds
• The star dichromatic number
• Chromatic properties of co-monostars
• The star chromatic index of hexagonal polyhexes
• scientific article; zbMATH DE number 3895095
• The circular chromatic index
• Chromatic index determined by fractional chromatic index
• Edge-magic indices of stars
• Geometric achromatic and pseudoachromatic indices

Cites work

• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• A note on Elkin's improvement of Behrend's construction
• Acyclic coloring of graphs
• Acyclic colorings of planar graphs
• Acyclic edge colorings of graphs
• Coloring with no 2-colored \(P_4\)'s
• Colouring a graph frugally
• Cycles Intersecting Edge-Cuts of Prescribed Sizes
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Star coloring of graphs
• The NP-Completeness of Edge-Coloring

Cited in

(41)

• The star-edge chromatic index on join-graph \(P_m\vee P_n\)
• Edge colorings avoiding patterns
• List star chromatic index of sparse graphs
• The skew chromatic index of a graph
• List star edge-coloring of subcubic graphs
• Edge colorings avoiding patterns
• Star edge coloring of corona product of path and wheel graph families
• A polynomial time algorithm to find the star chromatic index of trees
• Star coloring of cubic graphs
• An upper bound on the star chromatic index of graphs with \(\varDelta\geqslant 7\)
• Proper edge colorings of planar graphs with rainbow \(C_4\)-s
• Star edge-coloring of square grids
• On color frames of stars and generalized matching numbers
• Chromatic index determined by fractional chromatic index
• List star edge-coloring of claw-free subcubic multigraphs
• The \(b\)-chromatic index of a graph
• Star edge coloring of graphs with \(\mathrm{Mad}(G)<\frac{14}{5}\)
• On star 5-colorings of sparse graphs
• List star edge coloring of sparse graphs
• List star edge coloring of generalized Halin graphs
• The chromatic index of ring graphs
• List star edge coloring of \(k\)-degenerate graphs
• 2-distance vertex-distinguishing index of subcubic graphs
• A note on a conjecture of star chromatic index for outerplanar graphs
• Upper bounds on list star chromatic index of sparse graphs
• List star edge-coloring of \(k\)-degenerate graphs and \(K_4\)-minor free graphs
• The star chromatic index of hexagonal polyhexes
• Star edge coloring of the Cartesian product of graphs
• Star chromatic index of subcubic graphs
• On a star chromatic index of subcubic graphs
• On the star chromatic index of generalized Petersen graphs
• Star edge-coloring of graphs with maximum degree four
• An upper bound for the choice number of star edge coloring of graphs
• A survey on star edge-coloring of graphs
• Proper edge colorings of Cartesian products with rainbow \(C_4\)-s
• Edge-partition and star chromatic index
• Star edge coloring of maximal outer plane graphs
• On star edge colorings of bipartite and subcubic graphs
• Star edge coloring of some classes of graphs
• scientific article; zbMATH DE number 7651161 (Why is no real title available?)
• Star 5-edge-colorings of subcubic multigraphs

This page was built for publication: Star Chromatic Index

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