Strong edge colorings of uniform graphs (Q1887640): Difference between revisions

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\).