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 proceedingConference contributionAcademicpeer-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 languageEnglish
Title of host publicationGraph-Theoretic Concepts in Computer Science - 40th International Workshop, WG 2014, Nouan-le-Fuzelier, France, June 25-27, 2014. Revised Selected Papers
EditorsDieter Kratsch, Ioan Todinca
PublisherSpringer Singapore
Pages201-213
Number of pages13
ISBN (Electronic)978-3-319-12340-0
ISBN (Print)978-3-319-12339-4
DOIs
Publication statusPublished - 2014
Externally publishedYes
Event40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014 - Nouan-le-Fuzelier, France
Duration: 25 Jun 201427 Jun 2014
Conference number: 40

Publication series

NameLecture Notes in Computer Science
PublisherSpringer
Volume8747

Conference

Conference40th International Workshop on Graph-Theoretic Concepts in Computer Science, WG 2014
Abbreviated titleWG
CountryFrance
CityNouan-le-Fuzelier
Period25/06/1427/06/14

Fingerprint

Dive into the research topics of 'Hadwiger number of graphs with small chordality'. Together they form a unique fingerprint.

Cite this