{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:33:00Z","timestamp":1787322780823,"version":"build-2736575974"},"reference-count":28,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[1998,2]]},"abstract":"<jats:p>A vertex (edge) coloring $\\phi:V\\rightarrow \\{1,2,\\ldots ,t\\}$ ($\\phi':E\\rightarrow \\{1,2,\\ldots,$ $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 {\\em vertex ranking number} $\\chi_{r}(G)$ ({\\em edge ranking number} $\\chi_{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 {\\sc Vertex Ranking} and {\\sc Edge Ranking} problems. It is shown that $\\chi_{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 $\\chi_{r}$ and the chromatic number $\\chi$ coincide on all induced subgraphs, show that $\\chi_{r}(G)=\\chi (G)$ implies $\\chi (G)=\\omega (G)$ (largest clique size), and give a formula for $\\chi_{r}'(K_n)$.<\/jats:p>","DOI":"10.1137\/s0895480195282550","type":"journal-article","created":{"date-parts":[[2003,6,11]],"date-time":"2003-06-11T11:12:06Z","timestamp":1055329926000},"page":"168-181","source":"Crossref","is-referenced-by-count":98,"title":["Rankings of Graphs"],"prefix":"10.1137","volume":"11","author":[{"given":"Hans L.","family":"Bodlaender","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jitender S.","family":"Deogun","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Klaus","family":"Jansen","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ton","family":"Kloks","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dieter","family":"Kratsch","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Haiko","family":"M\u00fcller","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zsolt","family":"Tuza","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,8,1]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793251219"},{"key":"R2","first-page":"1","volume":"11","author":"Bodlaender H.","year":"1993","journal-title":"Acta Cybernet."},{"key":"R3","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1995.1009"},{"key":"R4","unstructured":", Graph theory with applications to algorithms and computer science, Proceedings of the fifth international conference held at Western Michigan University, Kalamazoo, Mich., June 4\u20138, 1984, A Wiley\u2010Interscience Publication, John Wiley & Sons Inc., 1985, 0\u20130, xv+81086g:05026"},{"key":"R5","unstructured":"A. Brandst\u00e4dt,\n                      Special Graph Classes \u2014 A Survey\n                      , Technical Report SM\u2010DU\u2010199, Schriftenreihe des FB Mathematik, Universit\u00e4t Duisburg, 1993."},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF01189071"},{"key":"R7","unstructured":"P. de la Torre, R. Greenlaw, and A. A. Sch\u00e4ffer,\n                      A Note on Deogun and Peng\u2019s Edge Ranking Algorithm\n                      , Technical Report 93\u201013, Dept. of Computer Science, Univ. of New Hampshire, Durham, NH, 1993."},{"key":"R8","doi-asserted-by":"crossref","unstructured":"J.Deogun, T.Kloks, D.Kratsch, H.M\u00fcller, On vertex ranking for permutation and other graphs, Lecture Notes in Comput. Sci., Vol. 775, Springer, Berlin, 1994, 747\u201375895d:05121","DOI":"10.1007\/3-540-57785-8_187"},{"key":"R9","unstructured":"JitenderDeogun, YipingPeng, Edge ranking of trees, Proceedings of the Twenty\u2010first Southeastern Conference on Combinatorics, Graph Theory, and Computing (Boca Raton, FL, 1990), Vol. 79, 1990, 19\u20132892i:05197"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1145\/356044.356047"},{"key":"R11","volume-title":"Computers and intractability","author":"Garey Michael","year":"1979"},{"key":"R12","volume-title":"Algorithmic graph theory and perfect graphs","author":"Golumbic Martin","year":"1980"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90194-9"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(91)90012-L"},{"key":"R15","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(93)E0216-Q"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"T. Kloks,\n                      Treewidth\u2013Computations and Approximations\n                      , Lecture Notes in Computer Science 842, Springer\u2010Verlag, New York, 1994.","DOI":"10.1007\/BFb0045375"},{"key":"R17","doi-asserted-by":"crossref","unstructured":"C. E. Leiserson,\n                      Area efficient graph layouts for VLSI\n                      , in Proc. 21st Annual IEEE Symposium on Foundations of Computer Science, 1980, IEEE Computer Society Press, Los Alamitos, CA, pp. 270\u2013281.","DOI":"10.1109\/SFCS.1980.13"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/0611010"},{"key":"R19","unstructured":"J. Nevins and D. Whitney, eds.\n                      Concurrent Design of Products and Processes\n                      , McGraw\u2010Hill, New York, 1989."},{"key":"R20","unstructured":"A. Pothen,\n                      The Complexity of Optimal Elimination Trees\n                      , Technical Report CS\u201088\u201013, Pennsylvania State University, University Park, PA, 1988."},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(90)90120-O"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1016\/0095-8956(86)90030-4"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(89)90161-0"},{"key":"R25","unstructured":"P. Scheffler,\n                      Node ranking and searching on graphs\n                      , in Proc. 3rd Twente Workshop on Graphs and Combinatorial Optimization, Memorandum No. 1132, U. Faigle and C. Hoede, eds., Faculty of Applied Mathematics, University of Twente, the Netherlands, 1993, abstract."},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90017-P"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9939-1962-0172273-0"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"X. Zhou, M. A. Kashem, and T. Nishizeki,\n                      Generalized edge\u2010rankings of trees\n                      , in Proc. 22nd Internat. Workshop Graph\u2010Theoretic Concepts in Computer Science (WG\u201996), Lecture Notes in Computer Science 1197, F. d\u2019Amore, P. G. Franciosa, and A. Marchetti\u2010Spaccamela, eds., Springer\u2010Verlag, Berlin, 1997, pp. 390\u2013404.","DOI":"10.1007\/3-540-62559-3_31"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0895480195282550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:25:42Z","timestamp":1787318742000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0895480195282550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[1998,2]]},"references-count":28,"journal-issue":{"issue":"1","published-print":{"date-parts":[[1998,2]]}},"alternative-id":["10.1137\/S0895480195282550"],"URL":"https:\/\/doi.org\/10.1137\/s0895480195282550","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[1998,2]]}}}