@inproceedings{05f9873af17c41fe9172a68e9a03dd62,
title = "Rankings of graphs",
abstract = "A vertex (edge) coloring c∶V → {1, 2, ⋯, t} (c′∶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. Among others 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 those 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(Kn).",
author = "Bodlaender, {H. L.} and Deogun, {J. S.} and K. Jansen and T. Kloks and D. Kratsch and H. M{\"u}ller and Zs Tuza",
year = "1995",
doi = "10.1007/3-540-59071-4_56",
language = "English (US)",
isbn = "3540590714",
series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",
publisher = "Springer Verlag",
pages = "292--304",
editor = "Mayr, {Ernst W.} and Gunther Schmidt and Gottfried Tinhofer",
booktitle = "Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings",
note = "20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1994 ; Conference date: 16-06-1994 Through 18-06-1994",
}