Finding Large Clique Minors is Hard

Authors

  • David Eppstein

DOI:

https://doi.org/10.7155/jgaa.00183

Keywords:

Graph minor , Hadwiger number , Clique , NP-complete

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.

Downloads

Download data is not yet available.

Downloads

Published

2009-02-01

How to Cite

Eppstein, D. (2009). Finding Large Clique Minors is Hard. Journal of Graph Algorithms and Applications, 13(2), 197–204. https://doi.org/10.7155/jgaa.00183

Issue

Vol. 13 No. 2 (2009)

Section

Articles

Categories

License

Copyright (c) 2009 David Eppstein

Creative Commons License

This work is licensed under a Creative Commons Attribution 4.0 International License.