Skip to main content
Article
Strong Chromatic Index of Subset Graphs
Journal of Graph Theory
  • Jennifer J. Quinn, University of Washington Tacoma
  • Arthur T. Benjamin
Publication Date
3-1-1997
Document Type
Article
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}_{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, Inc.

DOI
10.1002/(SICI)1097-0118(199703)23:3<267::AID-JGT8>3.0.CO;2-N
Publisher Policy
pre-print, post-print (with 12 month embargo)
Citation Information
Jennifer J. Quinn and Arthur T. Benjamin. "Strong Chromatic Index of Subset Graphs" Journal of Graph Theory Vol. 24 Iss. 3 (1997) p. 267 - 273
Available at: http://works.bepress.com/jennifer_quinn/23/