Strong edge colorings of uniform graphs

Andrzej Czygrinow, Brendan Nagle

Research output: Contribution to journalArticlepeer-review

1 Scopus citations


For a graph G = (V(G), E(G)), a strong edge coloring of G is an edge coloring in which every color class is an induced matching. The strong chromatic index of G, χs (G), is the smallest number of colors in a strong edge coloring of G. The strong chromatic index of the random graph G(n, p) was considered in Discrete Math. 281 (2004) 129, Austral. J. Combin. 10 (1994) 97, Austral. J. Combin. 18 (1998) 219 and Combin. Probab. Comput. 11 (1) (2002) 103. In this paper, we consider χS(G) for a related class of graphs G known as uniform or ε-regular graphs. In particular, we prove that for 0 < ε ≪ d < 1, all (d, ε)-regular bipartite graphs G = (U ∪ V, E) with |U| = |V|≥n0(d, ε) satisfy χ s(G)≤ξ(ε)δ(G)2, where ξ(ε) → 0 as → 0 (this order of magnitude is easily seen to be best possible). Our main tool in proving this statement is a powerful packing result of Pippenger and Spencer (Combin. Theory Ser. A 51(1) (1989) 24).

Original languageEnglish (US)
Pages (from-to)219-223
Number of pages5
JournalDiscrete Mathematics
Issue number3
StatePublished - Sep 28 2004


  • Strong chromatic index
  • The regularity lemma

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics


Dive into the research topics of 'Strong edge colorings of uniform graphs'. Together they form a unique fingerprint.

Cite this