Rankings of graphs

H. L. Bodlaender; J. S. Deogun; K. Jansen; T. Kloks; D. Kratsch; H. Müller; Zs Tuza

doi:10.1007/3-540-59071-4_56

Rankings of graphs

H. L. Bodlaender, J. S. Deogun, K. Jansen, T. Kloks, D. Kratsch, H. Müller, Zs Tuza

Computer Science and Engineering

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

19 Scopus citations

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(K_n).

Original language	English (US)
Title of host publication	Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings
Editors	Ernst W. Mayr, Gunther Schmidt, Gottfried Tinhofer
Publisher	Springer Verlag
Pages	292-304
Number of pages	13
ISBN (Print)	3540590714, 9783540590712
DOIs	https://doi.org/10.1007/3-540-59071-4_56
State	Published - 1995
Event	20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1994 - Herrsching, Germany Duration: Jun 16 1994 → Jun 18 1994

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	903
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Other

Other	20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1994
Country/Territory	Germany
City	Herrsching
Period	6/16/94 → 6/18/94

ASJC Scopus subject areas

Theoretical Computer Science
Computer Science(all)

Access to Document

10.1007/3-540-59071-4_56

Cite this

Bodlaender, H. L., Deogun, J. S., Jansen, K., Kloks, T., Kratsch, D., Müller, H., & Tuza, Z. (1995). Rankings of graphs. In E. W. Mayr, G. Schmidt, & G. Tinhofer (Eds.), Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings (pp. 292-304). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 903). Springer Verlag. https://doi.org/10.1007/3-540-59071-4_56

Rankings of graphs. / Bodlaender, H. L.; Deogun, J. S.; Jansen, K.; Kloks, T.; Kratsch, D.; Müller, H.; Tuza, Zs.

Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings. ed. / Ernst W. Mayr; Gunther Schmidt; Gottfried Tinhofer. Springer Verlag, 1995. p. 292-304 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 903).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Bodlaender, HL, Deogun, JS, Jansen, K, Kloks, T, Kratsch, D, Müller, H & Tuza, Z 1995, Rankings of graphs. in EW Mayr, G Schmidt & G Tinhofer (eds), Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 903, Springer Verlag, pp. 292-304, 20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1994, Herrsching, Germany, 6/16/94. https://doi.org/10.1007/3-540-59071-4_56

Bodlaender HL, Deogun JS, Jansen K, Kloks T, Kratsch D, Müller H et al. Rankings of graphs. In Mayr EW, Schmidt G, Tinhofer G, editors, Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings. Springer Verlag. 1995. p. 292-304. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). https://doi.org/10.1007/3-540-59071-4_56

Bodlaender, H. L. ; Deogun, J. S. ; Jansen, K. ; Kloks, T. ; Kratsch, D. ; Müller, H. ; Tuza, Zs. / Rankings of graphs. Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings. editor / Ernst W. Mayr ; Gunther Schmidt ; Gottfried Tinhofer. Springer Verlag, 1995. pp. 292-304 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@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",

}

TY - GEN

T1 - Rankings of graphs

AU - Bodlaender, H. L.

AU - Deogun, J. S.

AU - Jansen, K.

AU - Kloks, T.

AU - Kratsch, D.

AU - Müller, H.

AU - Tuza, Zs

PY - 1995

Y1 - 1995

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=21844482302&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=21844482302&partnerID=8YFLogxK

U2 - 10.1007/3-540-59071-4_56

DO - 10.1007/3-540-59071-4_56

M3 - Conference contribution

AN - SCOPUS:21844482302

SN - 3540590714

SN - 9783540590712

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 292

EP - 304

BT - Graph-Theoretic Concepts in Computer Science - 20th International Workshop, WG 1994, Proceedings

A2 - Mayr, Ernst W.

A2 - Schmidt, Gunther

A2 - Tinhofer, Gottfried

PB - Springer Verlag

T2 - 20th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 1994

Y2 - 16 June 1994 through 18 June 1994

ER -

Rankings of graphs

Abstract

Publication series

Other

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this