Ordered coloring of grids and related graphs
| Autor: | Valia Mitsou, Stathis Zachos, Michael Lampis, Panagiotis Cheilaris, Amotz Bar-Noy |
|---|---|
| Rok vydání: | 2012 |
| Předmět: |
Discrete mathematics
Vertex ranking General Computer Science Grid graph Ordered coloring ComputingMethodologies_IMAGEPROCESSINGANDCOMPUTERVISION Complete coloring Brooks' theorem Theoretical Computer Science Combinatorics Greedy coloring Edge coloring Indifference graph Graph coloring Fractional coloring List coloring Mathematics Computer Science(all) |
| Zdroj: | Theoretical Computer Science. 444:40-51 |
| ISSN: | 0304-3975 |
| DOI: | 10.1016/j.tcs.2012.04.036 |
| Popis: | 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. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect