## Abstract

A vertex (edge) coloring Φ : V → {1, 2,...,t} (Φ′ : E → {1, 2,..., t}) of a graph G = (V, E) is a vertex (edge) t-ranking if, for any two vertices (edges) of the same color, every path between them contains a vertex (edge) of larger color. The vertex ranking number χ_{r}(G) (edge ranking number χ′_{r}(G)) is the smallest value of t such that G has a vertex (edge) t-ranking. In this paper we study the algorithmic complexity of the VERTEX RANKING and EDGE RANKING problems. It is shown that χ_{r}(G) can be computed in polynomial time when restricted to graphs with treewidth at most k for any fixed k. We characterize the graphs where the vertex ranking number χ_{r}and the chromatic number χ coincide on all induced subgraphs, show that χ_{r}(G) = χ(G) implies χ(G) = ω(G) (largest clique size), and give a formula for χ′_{r}(K_{n}).

Original language | English (US) |
---|---|

Pages (from-to) | 168-181 |

Number of pages | 14 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 11 |

Issue number | 1 |

DOIs | |

State | Published - Feb 1998 |

## Keywords

- Edge ranking
- Graph algorithms
- Graph coloring
- Ranking of graphs
- Treewidth
- Vertex ranking

## ASJC Scopus subject areas

- Mathematics(all)