Premium
Optimal edge coloring of large graphs
Author(s) -
Gómez J.,
Escudero M.
Publication year - 1999
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/(sici)1097-0037(199908)34:1<61::aid-net6>3.0.co;2-g
Subject(s) - chordal graph , indifference graph , combinatorics , pathwidth , edge coloring , cograph , graph product , mathematics , brooks' theorem , 1 planar graph , graph coloring , discrete mathematics , computer science , graph , line graph , graph power
Most of the general families of large considered graphs in the context of the so‐called(Δ, D ) problem—that is, how to obtain graphs with maximum order, given their maximum degree Δ and their diameter D —known up to now for any value of Δ 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 Δ. Optimal edge coloring of large (Δ, 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 ≤ D ≤ 10. © 1999 John Wiley & Sons, Inc. Networks 34: 61–65, 1999