Star Chromatic Index
From MaRDI portal
Publication:4916092
DOI10.1002/JGT.21644zbMATH Open1262.05049arXiv1011.3376OpenAlexW2154102540MaRDI 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)
Abstract: The star chromatic index of a graph 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 . Our best lower bound on in terms of is 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.
Full work available at URL: https://arxiv.org/abs/1011.3376
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
- An improved construction of progression-free sets
- The NP-Completeness of Edge-Coloring
- Acyclic colorings of planar graphs
- Acyclic edge colorings of graphs
- Acyclic coloring of graphs
- Title not available (Why is that?)
- Coloring with no 2-colored \(P_4\)'s
- Star coloring of graphs
- Cycles Intersecting Edge-Cuts of Prescribed Sizes
- On Sets of Integers Which Contain No Three Terms in Arithmetical Progression
- Colouring a graph frugally
- A note on Elkin's improvement of Behrend's construction
Cited In (35)
- 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 Edge Coloring of Some Classes of Graphs
- Star edge-coloring of graphs with maximum degree four
- An upper bound for the choice number of 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 corona product of path and wheel graph families
- Star Edge Coloring of the Cartesian Product of Graphs
- 2-distance vertex-distinguishing index of subcubic graphs
- On a star chromatic index of subcubic graphs
- The star-edge chromatic index on join-graph \(P_m\vee P_n\)
- Edge colorings avoiding patterns
- Edge colorings avoiding patterns
- List star edge-coloring of \(k\)-degenerate graphs and \(K_4\)-minor free graphs
- Star chromatic index of subcubic 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 graphs with Mad(G)< 14/5
- Title not available (Why is that?)
- 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 5-edge-colorings of subcubic multigraphs
- List star chromatic index of sparse graphs
- Star edge coloring of maximal outer plane 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)
