On the strong chromatic index of cyclic multigraphs

DOI10.1016/S0166-218X(99)00123-7MaRDI QIDQ1962032zbMATH OpenWikidataFDO

Authors Pavol Gvozdjak, Mariusz Meszka, Zdzisław Skupień, Peter Horák

Publication date 30 January 2000

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0166-218X(99)00123-7

zbMATH Keywords

induced matchingmultigraphstrong chromatic index

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Review text

The strong chromatic index \(\text{sq}(G)\) of a multigraph \(G\) is the smallest number of colours needed to colour the edges of \(G\) so that each colour class is an induced matching. The largest size of a submultigraph of \(G\) without any induced matching of size two is denoted by \(\eta(G)\). A cyclic multigraph is a multigraph whose underlying graph is a cycle. Results providing exact values or upper bounds for \(\text{sq}(G)\) where \(G\) is a cycling multigraphs are shown. The often involve the parameter \(\eta(G)\).

Recommendations

• scientific article; zbMATH DE number 1501957
• Strong chromatic index of subcubic planar multigraphs
• scientific article; zbMATH DE number 4187830
• scientific article; zbMATH DE number 4177085

Cites work

• scientific article; zbMATH DE number 3882451 (Why is no real title available?)
• scientific article; zbMATH DE number 3851125 (Why is no real title available?)
• scientific article; zbMATH DE number 3265667 (Why is no real title available?)
• scientific article; zbMATH DE number 3308991 (Why is no real title available?)
• scientific article; zbMATH DE number 3400923 (Why is no real title available?)
• scientific article; zbMATH DE number 4187830 (Why is no real title available?)
• Induced matchings in bipartite graphs
• Induced matchings in cubic graphs
• Problems and results in combinatorial analysis and graph theory
• Some maximum multigraphs and adge/vertex distance colourings
• The strong chromatic index of a cubic graph is at most 10

Cited in

(5)

• scientific article; zbMATH DE number 4208096 (Why is no real title available?)
• Chromatic Edge Strength of Some Multigraphs
• scientific article; zbMATH DE number 1501957 (Why is no real title available?)
• Strong chromatic index of subcubic planar multigraphs
• BCH codes and distance multi- or fractional colorings in hypercubes asymptotically

This page was built for publication: On the strong chromatic index of cyclic multigraphs

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