Hadwiger number of graphs with small chordality

Petr A. Golovach; Pinar Heggernes; Pim van 't Hof; Christophe Paul

doi:10.1007/978-3-319-12340-0_17

Hadwiger number of graphs with small chordality

Petr A. Golovach, Pinar Heggernes, Pim van 't Hof, Christophe Paul

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

4 Citations (Scopus)

Abstract

The Hadwiger number of a graph G is the largest integer h such that G has the complete graph Kh as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s . We show that this problem can be solved in polynomial time on AT-free graphs when s≥2 , but is NP-hard on chordal graphs for every fixed s≥2 .

Original language	English
Title of host publication	Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
Editors	Dieter Kratsch, Ioan Todinca
Publisher	Springer
Pages	201-213
Number of pages	13
ISBN (Electronic)	978-3-319-12340-0
ISBN (Print)	978-3-319-12339-4
DOIs	https://doi.org/10.1007/978-3-319-12340-0_17
Publication status	Published - 2014
Externally published	Yes
Event	40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 - Nouan-le-Fuzelier, France Duration: 25 Jun 2014 → 27 Jun 2014 Conference number: 40

Publication series

Name	Lecture Notes in Computer Science
Publisher	Springer
Volume	8747

Conference

Conference	40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014
Abbreviated title	WG
Country/Territory	France
City	Nouan-le-Fuzelier
Period	25/06/14 → 27/06/14

Access to Document

10.1007/978-3-319-12340-0_17

Cite this

Golovach, P. A., Heggernes, P., van 't Hof, P., & Paul, C. (2014). Hadwiger number of graphs with small chordality. In D. Kratsch, & I. Todinca (Eds.), Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers (pp. 201-213). (Lecture Notes in Computer Science; Vol. 8747). Springer. https://doi.org/10.1007/978-3-319-12340-0_17

Golovach, Petr A. ; Heggernes, Pinar ; van 't Hof, Pim et al. / Hadwiger number of graphs with small chordality. Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. editor / Dieter Kratsch ; Ioan Todinca. Springer, 2014. pp. 201-213 (Lecture Notes in Computer Science).

@inproceedings{422da31e308d49c79f5946d6b9fa218e,

title = "Hadwiger number of graphs with small chordality",

abstract = "The Hadwiger number of a graph G is the largest integer h such that G has the complete graph Kh as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s . We show that this problem can be solved in polynomial time on AT-free graphs when s≥2 , but is NP-hard on chordal graphs for every fixed s≥2 .",

author = "Golovach, \{Petr A.\} and Pinar Heggernes and \{van 't Hof\}, Pim and Christophe Paul",

year = "2014",

doi = "10.1007/978-3-319-12340-0\_17",

language = "English",

isbn = "978-3-319-12339-4",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "201--213",

editor = "Dieter Kratsch and Ioan Todinca",

booktitle = "Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers",

address = "Germany",

note = "40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, WG ; Conference date: 25-06-2014 Through 27-06-2014",

}

Golovach, PA, Heggernes, P, van 't Hof, P & Paul, C 2014, Hadwiger number of graphs with small chordality. in D Kratsch & I Todinca (eds), Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. Lecture Notes in Computer Science, vol. 8747, Springer, pp. 201-213, 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014, Nouan-le-Fuzelier, France, 25/06/14. https://doi.org/10.1007/978-3-319-12340-0_17

Hadwiger number of graphs with small chordality. / Golovach, Petr A.; Heggernes, Pinar; van 't Hof, Pim et al.
Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. ed. / Dieter Kratsch; Ioan Todinca. Springer, 2014. p. 201-213 (Lecture Notes in Computer Science; Vol. 8747).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › Academic › peer-review

TY - GEN

T1 - Hadwiger number of graphs with small chordality

AU - Golovach, Petr A.

AU - Heggernes, Pinar

AU - van 't Hof, Pim

AU - Paul, Christophe

N1 - Conference code: 40

PY - 2014

Y1 - 2014

N2 - The Hadwiger number of a graph G is the largest integer h such that G has the complete graph Kh as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s . We show that this problem can be solved in polynomial time on AT-free graphs when s≥2 , but is NP-hard on chordal graphs for every fixed s≥2 .

AB - The Hadwiger number of a graph G is the largest integer h such that G has the complete graph Kh as a minor. We show that the problem of determining the Hadwiger number of a graph is NP-hard on co-bipartite graphs, but can be solved in polynomial time on cographs and on bipartite permutation graphs. We also consider a natural generalization of this problem that asks for the largest integer h such that G has a minor with h vertices and diameter at most s . We show that this problem can be solved in polynomial time on AT-free graphs when s≥2 , but is NP-hard on chordal graphs for every fixed s≥2 .

U2 - 10.1007/978-3-319-12340-0_17

DO - 10.1007/978-3-319-12340-0_17

M3 - Conference contribution

SN - 978-3-319-12339-4

T3 - Lecture Notes in Computer Science

SP - 201

EP - 213

BT - Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers

A2 - Kratsch, Dieter

A2 - Todinca, Ioan

PB - Springer

T2 - 40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014

Y2 - 25 June 2014 through 27 June 2014

ER -

Golovach PA, Heggernes P, van 't Hof P, Paul C. Hadwiger number of graphs with small chordality. In Kratsch D, Todinca I, editors, Graph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers. Springer. 2014. p. 201-213. (Lecture Notes in Computer Science). doi: 10.1007/978-3-319-12340-0_17

Hadwiger number of graphs with small chordality

Abstract

Publication series

Conference

Access to Document

Fingerprint

Cite this