Finding Large Clique Minors is Hard
Vol. 13, no. 2, pp. 197-204, 2009. Concise paper.
Abstract We prove that it is NP-complete, given a graph G and a parameter h, to determine whether G contains a complete graph Kh as a minor.
Submitted: June 2008.
Reviewed: April 2009.
Revised: May 2009.
Accepted: July 2009.
Final: July 2009.
Published: July 2009.
Communicated by Giuseppe Liotta
article (PDF)