Ordered Coloring for Grids and Related Graphs
2011 (English)In: Theoretical Computer Science, ISSN 0304-3975Article in journal (Refereed) Submitted
We investigate a coloring problem, called ordered coloring, in grids and some other families of grid-like graphs. Ordered coloring (also known as vertex ranking) is related to conflict-free coloring and other traditional coloring problems. Such coloring problems can model (among others) efficient frequency assignments in cellular networks. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs. To the best of our knowledge, this is the first attempt to calculate exactly the ordered chromatic number of these graph families.
Place, publisher, year, edition, pages
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-58602OAI: oai:DiVA.org:kth-58602DiVA: diva2:473411
QS 201203162012-01-052012-01-052012-03-16Bibliographically approved