Star Chromatic Index

DOI10.1002/JGT.21644MaRDI QIDQ4916092zbMATH OpenOpenAlexFDO

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)

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

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)