Ordered coloring of grids and related graphs

详细信息	查看全文 | 推荐本文 |

• 作者：Amotz Bar-Noy^a ; ^b ; ^{amotz@sci.brooklyn.cuny.edu} ; Panagiotis Cheilaris^c ; ^{panagiot@math.bgu.ac.il} ; Michael Lampis^b ; ^{mlampis@gc.cuny.edu} ; Valia Mitsou^b ; ^{vmitsou@cs.gc.cuny.edu} ; Stathis Zachos^a ; ^b ; ^d ; ^{zachos@cs.ntua.gr}
• 关键词：Grid graph ; Ordered coloring ; Vertex ranking
• 刊名：Theoretical Computer Science
• 出版年：2012
• 期刊代码：114_03043975
• 类别：cp
• 出版时间：27 July, 2012
• 卷：444
• 期：Complete
• 页码：40-51
• 文件大小：467 K

摘要

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.