Strong Chromatic Index of Subset Graphs

Document Type



Mathematics (HMC)

Publication Date



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.

Rights Information

© 1997 John Wiley & Sons