Strong chromatic index of k-degenerate graphs

DOI10.1016/J.DISC.2014.04.016MaRDI QIDQ2017054zbMATH OpenOpenAlexFDO

Authors Tao Wang

Publication date 25 June 2014

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

\(k\)-degenerate graphchordless graphminimally 2-connected graphstrong chromatic index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Connectivity (05C40)

Abstract: A {em strong edge coloring} of a graph $G$ is a proper edge coloring in which every color class is an induced matching. The {em strong chromatic index} $chiu{p}_{s^{\prime }}(G)$ of a graph $G$ is the minimum number of colors in a strong edge coloring of $G$. In this note, we improve a result by D{k e}bski etal [Strong chromatic index of sparse graphs, arXiv:1301.1992v1] and show that the strong chromatic index of a $k$-degenerate graph $G$ is at most $(4k-2)cdotDelta(G)-2k^2+1$. As a direct consequence, the strong chromatic index of a $2$-degenerate graph $G$ is at most $6Delta(G)-7$, which improves the upper bound $10Delta(G)-10$ by Chang and Narayanan [Strong chromatic index of 2-degenerate graphs, J. Graph Theory 73 (2013) (2) 119--126]. For a special subclass of $2$-degenerate graphs, we obtain a better upper bound, namely if $G$ is a graph such that all of its $3^{+}$-vertices induce a forest, then $chiu{p}_{s^{\prime }}(G)leq4Delta(G)-3$; as a corollary, every minimally $2$-connected graph $G$ has strong chromatic index at most $4Delta(G)-3$. Moreover, all the results in this note are best possible in some sense.

Recommendations

• Strong edge-coloring of 2-degenerate graphs
• Strong edge-colorings for \(k\)-degenerate graphs
• The strong chromatic index of sparse graphs
• Strong chromatic index of sparse graphs
• Strong edge-colorings of sparse graphs with large maximum degree

Cites work

• scientific article; zbMATH DE number 2123255 (Why is no real title available?)
• Problems and results in combinatorial analysis and graph theory
• Strong chromatic index of 2-degenerate graphs
• Strong edge-colorings for \(k\)-degenerate graphs

Cited in

(16)

• On the precise value of the strong chromatic index of a planar graph with a large girth
• A note on strong edge coloring of sparse graphs
• Note on injective edge-coloring of graphs
• List strong edge-coloring of graphs with maximum degree 4
• Strong edge-colorings of sparse graphs with large maximum degree
• Strong chromatic index of K₄-minor free graphs
• List star edge-coloring of \(k\)-degenerate graphs and \(K_4\)-minor free graphs
• Strong chromatic index of sparse graphs
• The strong chromatic index of sparse graphs
• Strong chromatic index of 2-degenerate graphs
• Strong edge-colorings for \(k\)-degenerate graphs
• Recent progress on strong edge-coloring of graphs
• Strong edge-coloring of 2-degenerate graphs
• The strong chromatic index of 1-planar graphs
• Edge-coloring of 2-degenerate graphs with induced-forest condition
• Strong chromatic index of \(K_{1, t}\)-free graphs

This page was built for publication: Strong chromatic index of \(k\)-degenerate graphs

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