Font size: Αα Αα Αα hide gadgets
You are here: Seminars » 2014-2015 » P. A. Golovach, 2014-10-17 { prev, contents, next } Anonymously browsing from at 02:24:12, 21-05-2018. login
download seminar details: { pdf }


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


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.


You must be logged in to comment.


Page updates

No recent updates.

Feeds RSS and Atom feeds

all posts RSS
news RSS
announcements RSS
website news RSS
all events RSS
defenses RSS
exams RSS
seminars RSS
graduations RSS
Web standards: XHTML1.0, CSS3.
© 1996 – 2018 MPLA: Graduate program in Logic, Algorithms and Computation.
Contact the webmaster.