Premium
On the complexity of distributed graph coloring with local minimality constraints
Author(s) -
Gavoille Cyril,
Klasing Ralf,
Kosowski Adrian,
Kuszner Łukasz,
Navarra Alfredo
Publication year - 2009
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/net.20293
Subject(s) - greedy coloring , fractional coloring , list coloring , combinatorics , complete coloring , vertex (graph theory) , mathematics , edge coloring , graph coloring , greedy algorithm , colored , graph , brooks' theorem , computer science , discrete mathematics , mathematical optimization , graph power , line graph , materials science , composite material
Abstract Distributed greedy coloring is an interesting and intuitive variation of the standard coloring problem. Given an order among the colors, a coloring is said to be greedy if there does not exist a vertex for which its associated color can be replaced by a color of lower position in the fixed order without violating the property that neighboring vertices must receive different colors. We consider the problems of Greedy Coloring and Largest First Coloring (a variant of greedy coloring with strengthened constraints) in the Linial model of distributed computation, providing lower and upper bounds and a comparison to the (Δ + 1)‐ Coloring and Maximal Independent Set problems, with Δ being the maximum vertex degree in G . © 2009 Wiley Periodicals, Inc. NETWORKS, 2009