Ordered Coloring Grids and Related Graphs
2009 (English)In: 16th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2009, 2009, 30-43 p.Conference paper (Refereed)
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
2009. 30-43 p.
, Lecture Notes in Computer Science, ISSN 03029743 ; 5869
ordered coloring, vertex ranking, conflict-free coloring
Computer and Information Science
IdentifiersURN: urn:nbn:se:kth:diva-58588DOI: 10.1007/978-3-642-11476-2_4ISBN: 978-364211475-5ISBN: 364211475XOAI: oai:DiVA.org:kth-58588DiVA: diva2:473390
16th International Colloquium on Structural Information and Communication Complexity, SIROCCO 2009, Piran, 25 May 2009 through 27 May 2009
QC 201201172012-01-052012-01-052012-01-17Bibliographically approved