Strong edge colorings of uniform graphs
type: Item
instance of: scholarly article
title: Strong edge colorings of uniform graphs
zbMATH Open document ID: 1059.05047
author: Andrzej Czygrinow
author: B. Nagle
published in: Discrete Mathematics
publication date: 2004-11-22T00:00:00Z
review text: A strong edge coloring of a graph is a (proper) edge coloring in which every color class is an induced matching. The strong chromatic index \(\chi_S(G)\) of a graph \(G\) is the minimum number of colors in a strong edge coloring of \(G\). For a bipartite graph \(G=(U\cup V, E)\), and for two nonempty sets \(U'\subseteq U\) and \(V'\subseteq V\), let \(E(U', V')\) denote the set of all edges in \(G\) between a vertex in \(U'\) and a vertex in \(V'\). Set \(d(U', V')=\frac{| E(U', V')| }{| U'| | V'| }\). For constant \(d\) and \(\varepsilon > 0\), a bipartite graph \(G=(U\cup V, E)\) is \((d, \varepsilon)\)-regular if, for all \(U'\subseteq U, | U'| >\varepsilon | U| \), and all \(V'\subseteq V, | V'| >\varepsilon | V| \), it holds that \(| d - d(U', V')| < \varepsilon\). The main result of the paper reads: For every \(0<d<1\) and \(\mu >0\), there exists \(\varepsilon >0\) and integer \(n_0\) such that, for all \((d, \varepsilon)\)-regular bipartite graphs \(G=(U\cup V, E)\) with \(| U| =| V| \geq n_0\), \(\chi_S(G)\leq \mu\Delta(G)^2\), where \(\Delta(G)\) is the maximum degree of \(G\).
reviewed by: Van Bang Le
Mathematics Subject Classification ID: 05C15
Mathematics Subject Classification ID: 05C65
zbMATH DE Number: 2117312
zbMATH Keywords: strong chromatic index
zbMATH Keywords: regularity lemma
MaRDI profile type: Publication
full work available at URL: j.disc.2004.04.011
OpenAlex ID: W2104919312
cites work: Perfect matchings in \(\varepsilon\)-regular graphs
cites work: Bounding the strong chromatic index of dense random graphs
cites work: Q4325283
cites work: Q5752590
cites work: On the number of perfect matchings and Hamilton cycles in \(\varepsilon\)-regular non-bipartite graphs
cites work: Q4519896
cites work: Q4878666
cites work: Strong chromatic index of subset graphs
cites work: Q4222086
cites work: Asymptotic behavior of the chromatic index for hypergraphs
cites work: On universality of graphs with uniformly distributed edges
cites work: Q4200109
cites work: A General Upper Bound on the List Chromatic Number of Locally Sparse Graphs
DOI: 10.1016/J.DISC.2004.04.011
description: scientific article; zbMATH DE number 2117312