Strong Chromatic Index of Subset Graphs

Authors

Jennifer J. Quinn, Occidental College
Arthur T. Benjamin, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

3-1997

Abstract

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

DOI

10.1002/(SICI)1097-0118(199703)23:3<267::AID-JGT8>3.0.CO;2-N

Recommended Citation

Quinn, J. J. and Benjamin, A. T. (1997), Strong chromatic index of subset graphs. J. Graph Theory, 24: 267–273.