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

edge coloringgraph 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

• 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
• scientific article; zbMATH DE number 1775440 (Why is no real title available?)
• On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
• Star coloring of graphs
• The NP-Completeness of Edge-Coloring

Cited in

(45)

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

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)