Rankings of graphs

Hans L. Bodlaender, Jitender S. Deogun, Klaus Jansen, Ton Kloks, Dieter Kratsch, Haiko Müller, Zsolt Tuza

Research output: Contribution to journalArticlepeer-review

125 Scopus citations

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 χrand 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).

Original languageEnglish (US)
Pages (from-to)168-181
Number of pages14
JournalSIAM Journal on Discrete Mathematics
Volume11
Issue number1
DOIs
StatePublished - Feb 1998

Keywords

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

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

Dive into the research topics of 'Rankings of graphs'. Together they form a unique fingerprint.

Cite this