The strong chromatic index of sparse graphs

DOI10.1016/J.IPL.2014.10.006MaRDI QIDQ477679zbMATHOpenAlexFDO

Authors Jarosław Grytczuk, Małgorzata Śleszyńska-Nowak, Michał Dębski

Publication date 9 December 2014

Published in Information Processing Letters (Search for Journal in Brave)

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

zbMATH Keywords

sparse graphscombinatorial problemsstrong chromatic indexstrong edge-coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Density (toughness, etc.) (05C42)

Abstract: A coloring of the edges of a graph $G$ is strong if each color class is an induced matching of $G$. The strong chromatic index of $G$, denoted by $ch{i}_s^{prime}(G)$, is the least number of colors in a strong edge coloring of $G$. In this note we prove that $ch{i}_s^{prime}(G)leq(4k-1)Delta(G)-k(2k+1)+1$ for every $k$-degenerate graph $G$. This confirms the strong version of conjecture stated recently by Chang and Narayanan [3]. Our approach allows also to improve the upper bound from [3] for chordless graphs. We get that $\mathrm{\%}ch{i}_s^{prime}(G)leq4Delta-3$ for any chordless graph $G$. Both bounds remain valid for the list version of the strong edge coloring of these graphs.

Recommendations

• Strong chromatic index of sparse graphs
• On the strong chromatic index of sparse graphs
• scientific article; zbMATH DE number 4187830
• The strong chromatic index of a class of graphs
• Strong chromatic index of chordless graphs
• The chromatic index of strongly regular graphs
• A bound on the strong chromatic index of a graph
• Strong chromatic index of subset graphs
• scientific article; zbMATH DE number 1501957

Cites work

• scientific article; zbMATH DE number 3609704 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• A bound on the strong chromatic index of a graph
• Incidence and strong edge colorings of graphs
• Induced matchings in bipartite graphs
• Nearly complete graphs decomposable into large induced matchings and their applications
• Strong chromatic index of \(k\)-degenerate graphs

Cited in

(20)

• A note on strong edge coloring of sparse graphs
• Strong chromatic index of 2-degenerate graphs
• Clique number of the square of a line graph
• Recent progress on strong edge-coloring of graphs
• Strong chromatic index of \(k\)-degenerate graphs
• Strong chromatic index of \(K_{1, t}\)-free graphs
• The chromatic index of strongly regular graphs
• Strong chromatic index of unit distance graphs
• Strong chromatic index of sparse graphs
• Strong edge-coloring of 2-degenerate graphs
• On the precise value of the strong chromatic index of a planar graph with a large girth
• The strong chromatic index of a class of graphs
• From edge-coloring to strong edge-coloring
• Strong edge-colorings for \(k\)-degenerate graphs
• Colouring exact distance graphs of chordal graphs
• Strong chromatic index of chordless graphs
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• Strong chromatic index of \(K_4\)-minor free graphs
• Strong edge coloring of circle graphs
• Strong cliques in claw-free graphs

This page was built for publication: The strong chromatic index of sparse graphs

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