Ordered coloring of grids and related graphs
2012 (English)In: Theoretical Computer Science, ISSN 0304-3975, Vol. 444, 40-51 p.Article in journal (Refereed) Published
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) has applications, among other areas, in efficient solving of sparse linear systems of equations and scheduling parallel assembly of products. Our main technical results improve upper and lower bounds for the ordered chromatic number of grids and related graphs.
Place, publisher, year, edition, pages
2012. Vol. 444, 40-51 p.
Grid graph, Ordered coloring, Vertex ranking
IdentifiersURN: urn:nbn:se:kth:diva-112877DOI: 10.1016/j.tcs.2012.04.036ISI: 000306041700005OAI: oai:DiVA.org:kth-112877DiVA: diva2:587530
QC 201305022013-01-142013-01-142013-05-02Bibliographically approved