A bound on the strong chromatic index of a graph
type: Item
instance of: scholarly article
title: A bound on the strong chromatic index of a graph
zbMATH Open document ID: 0880.05036
published in: Journal of Combinatorial Theory. Series B
publication date: 1997-05-05T00:00:00Z
full work available at URL: http://hdl.handle.net/1807/9474
review text: The strong chromatic index \(s\chi'(G)\) of a graph \(G\) is the minimum number of colors in a proper edge coloring of a graph in which no edge is adjacent to an edge of the same color. It is proved that \(s\chi'(G)\leq 1.998\Delta^2\), where \(\Delta\) is the maximum degree of a vertex of \(G\). This answers a question of Erdös and Nešetřil, which was to show that there exists an \(\varepsilon>0\) such that \(s\chi'(G)\leq(2- \varepsilon)\Delta^2\). It is conjectured that, in fact, \(s\chi'(G)\leq{5\over 4}\Delta^2\), with the extremal example being the graph obtained from a \(C_5\) by replacing each vertex with a large independent set and each edge by the appropriate complete bipartite graph.
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C35
zbMATH DE Number: 1006751
zbMATH Keywords: extremal graph
zbMATH Keywords: strong chromatic index
author: Michael Molloy
author: Bruce Reed
reviewed by: Ralph Faudree
MaRDI profile type: Publication
OpenAlex ID: W2048352893
cites work: Q4004078
cites work: The strong chromatic index of a cubic graph is at most 10
cites work: The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
cites work: Q4074927
cites work: Induced matchings in bipartite graphs
cites work: Q5752590
cites work: Q3201075
cites work: Induced matchings in cubic graphs
cites work: 25 pretty graph colouring problems
cites work: Q4866087
cites work: Concentration of measure and isoperimetric inequalities in product spaces
DOI: 10.1006/JCTB.1997.1724
description: scientific article; zbMATH DE number 1006751