Pim van 't Hof

Hadwiger number of graphs with small chordality

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

SIAM Journal on Discrete Mathematics, vol. 29, no. 3, pp. 1427-1451, 2015.
[DOI] [Preprint]

A preliminary version of this paper will appear in the proceedings of WG 2014, the 40th International Workshop on Graph-Theoretic Concepts in Computer Science (held on June 25-27, 2014 in Le Domaine de Chalès, France), Lecture Notes in Computer Science, vol. 8747, pp. 201-213, 2014.
[DOI]

Abstract:

The Hadwiger number of a graph G is the largest integer h such that G has the complete graph K_h 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.