A note on the strong chromatic index of bipartite graphs
type: Item
instance of: scholarly article
title: A note on the strong chromatic index of bipartite graphs
zbMATH Open document ID: 1155.05026
published in: Discrete Mathematics
publication date: 2008-07-11T00:00:00Z
review text: A strong edge-coloring of a graph \(G\) is an edge-coloring in which every color class is an induced matching; that is, if edges \(uv\) and \(wz\) have the same color, then the pair \(uw, uz, vw\) and \(vz\) are all non-edges of \(G\). The strong chromatic index \(s'(G)\) is the minimum number of colors in a strong edge-coloring of \(G\). Let \(G\) be a bipartite graph such that \(\Delta_1\) and \(\Delta_2\) are the maximum degrees among vertices in the two partite sets, respectively. A conjecture proposed by Brualdi and Quinn states that \(s'(G)\) is bounded by \(\Delta_1\Delta_2\). The author of this paper gives affirmative answer to this conjecture for the case \(\Delta_1=2\).
Mathematics Subject Classification ID: 05C15
zbMATH DE Number: 5300692
zbMATH Keywords: strong edge-coloring
zbMATH Keywords: induced matching
zbMATH Keywords: bipartite graph
author: Kittikorn Nakprasit
MaRDI profile type: Publication
full work available at URL: j.disc.2007.07.034
OpenAlex ID: W2085014006
cites work: The strong chromatic index of a cubic graph is at most 10
cites work: Q3039368
cites work: Incidence and strong edge colorings of graphs
cites work: The maximum number of edges in \(2K_ 2\)-free graphs of bounded degree
cites work: Induced matchings in bipartite graphs
cites work: Induced matchings in cubic graphs
cites work: Strong chromatic index of subset graphs
cites work: Strong chromatic index in subset graphs
cites work: On induced matchings
DOI: 10.1016/J.DISC.2007.07.034
description: scientific article; zbMATH DE number 5300692