mpla.math.uoa.gr
Font size: Αα Αα Αα hide gadgets
You are here: Seminars » 2014-2015 » P. A. Golovach, 2014-10-17 { prev, contents, next }
download seminar details: { pdf }

Seminar

Photo of Golovach
Speaker: Petr A. Golovach (Петр А. Головач)
Title: Hadwiger number of graphs with small chordality
Date: Friday, 17 Oct 2014
Time: 18:30-19:20
Location: Univeristy of Athens, Department of Mathematics, University of Athens, room Γ33

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>1, but is NP-hard on chordal graphs for every fixed s>1.

Comments

You must be logged in to comment.

Reporter

Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.