Strong Chromatic Index of Subset Graphs
The strong chromatic index of a graph G, denoted sq(G), is the minimum number of parts needed to partition the edges of G into induced matchings. For 0 ≤ k ≤ l ≤ m, the subset graph Sm(k, l) is a bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. We show that sq(Sm(k, l) ) = m choose l-k and that this number satisfies the strong chromatic index conjecture by Brualdi and Quinn for bipartite graphs. Further, we demonstrate that the conjecture is also valid for a more general family of bipartite graphs.
© 1997 John Wiley & Sons
Quinn, J. J. and Benjamin, A. T. (1997), Strong chromatic index of subset graphs. J. Graph Theory, 24: 267–273.