Some Graph-Colouring Theorems with Applications to Generalized Connection Networks

Authors

David G. Kirkpatrick, University of British Columbia
Maria M. Klawe, Harvey Mudd College
Nicholas Pippenger, Harvey Mudd CollegeFollow

Document Type

Article

Department

Mathematics (HMC)

Publication Date

1985

Abstract

With the aid of a new graph-colouring theorem, we give a simple explicit construction for generalized n-connectors with 2k - 1 stages and O( n^{1 + 1 / k} (log n )^{( k - 1)/ 2} ) edges. This is asymptotically the best explicit construction known for generalized connectors.

Rights Information

© 1985 Society for Industrial and Applied Mathematics

Recommended Citation

Kirkpatrick, David G., Maria Klawe, and Nicholas Pippenger. “Some Graph-Colouring Theorems with Applications to Generalized Connection Networks.” SIAM Journal on Algebraic and Discrete Methods 6, no. 4 (October 1985): 576-582.