The strong chromatic index of sparse graphs

DOI10.1016/J.IPL.2014.10.006zbMATH Open1304.05043arXiv1301.1992OpenAlexW1997772282MaRDI QIDQ477679FDOQ477679

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

Publication date: 9 December 2014

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

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.

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

Recommendations

• Strong chromatic index of sparse graphs
• On the strong chromatic index of sparse graphs
• [[:Publication:5752590|Title not available (Why is that?)]]
• 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
• [[:Publication:4503093|Title not available (Why is that?)]]
• The strong chromatic index of graphs and subdivisions

zbMATH Keywords

sparse graphscombinatorial problemsstrong chromatic indexstrong edge-coloring

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Incidence and strong edge colorings of graphs
• A bound on the strong chromatic index of a graph
• Title not available (Why is that?)
• Induced matchings in bipartite graphs
• Strong chromatic index of \(k\)-degenerate graphs
• Nearly complete graphs decomposable into large induced matchings and their applications

Cited In (13)

• Strong chromatic index of unit distance graphs
• A Combinatorial Classic — Sparse Graphs with High Chromatic Number
• Strong edge coloring of circle graphs
• Clique number of the square of a line graph
• Strong chromatic index of sparse graphs
• On the precise value of the strong chromatic index of a planar graph with a large girth
• Strong cliques in claw-free graphs
• Strong chromatic index of \(K_{1, t}\)-free graphs
• Colouring exact distance graphs of chordal graphs
• Strong chromatic index of \(K_4\)-minor free graphs
• A note on strong edge coloring of sparse graphs
• Recent progress on strong edge-coloring of graphs
• Strong edge-coloring of 2-degenerate 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)