Optimal edge coloring of large graphs
Most of the general families of large considered graphs in the context of the so-called (Delta, D) problem - that is, how to obtain graphs with maximum order, given their maximum degree Delta and their diameter D-known up to now for any value of Delta and D, are obtained as product graphs, compound graphs, and generalized compound graphs. It is shown that many of these graph constructions have a minimum chromatic index Delta. Optimal edge coloring of large (Delta, D) graphs is interesting, for instance, for the design of large packet radio networks. Furthermore, a complete table with the best-known edge-colored large graphs is also presented for 2 less than or equal to D less than or equal to 10. (C) 1999 John Wiley & Sons, Inc. Networks 34: 61-65, 1999.
edge coloring large graphs compound graphs chromatic index packet radio networks interconnection networks