{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:21:15Z","timestamp":1787322075750,"version":"build-2736575974"},"reference-count":23,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2015,1]]},"abstract":"<jats:p>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 \\sf 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\\geq 2$ but is \\sf NP-hard on chordal graphs for every fixed $s\\geq 2$.<\/jats:p>","DOI":"10.1137\/140975279","type":"journal-article","created":{"date-parts":[[2015,8,11]],"date-time":"2015-08-11T12:24:23Z","timestamp":1439295863000},"page":"1427-1451","source":"Crossref","is-referenced-by-count":5,"title":["Hadwiger Number of Graphs with Small Chordality"],"prefix":"10.1137","volume":"29","author":[{"given":"Petr A.","family":"Golovach","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pinar","family":"Heggernes","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Pim","family":"van 't Hof","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Christophe","family":"Paul","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2015,8,11]]},"reference":[{"key":"atypb1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2006.12.021"},{"key":"atypb2","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(80)80001-1"},{"key":"atypb3","unstructured":"A. Brandsta\u0308dt, V.B. Le, and J. P. Spinrad,\n                      Graph Classes: A Survey\n                      , SIAM Monographs on Discrete Mathematics and Applications, SIAM, Philadelphia, 1999."},{"key":"atypb4","doi-asserted-by":"crossref","unstructured":"L. Cai and C. Guo,\n                      Contracting few edges to remove forbidden induced subgraphs\n                      , in Proceedings of IPEC 2013, Lecture Notes in Comput. Sci. 8246, Springer, New York, 2013, pp. 97-109.","DOI":"10.1007\/978-3-319-03898-8_10"},{"key":"atypb5","first-page":"145","volume":"1","author":"Corneil D. G.","year":"1981","journal-title":"Ann. Discrete Math."},{"key":"atypb6","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480193250125"},{"key":"atypb7","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795282377"},{"key":"atypb8","doi-asserted-by":"publisher","DOI":"10.1137\/0214065"},{"key":"atypb9","doi-asserted-by":"crossref","unstructured":"R. G. Downey and M. R. Fellows,\n                      Fundamentals of Parameterized Complexity\n                      , Texts Comput. Sci., Springer, New York, 2013.","DOI":"10.1007\/978-1-4471-5559-1"},{"key":"atypb10","doi-asserted-by":"publisher","DOI":"10.7155\/jgaa.00183"},{"key":"atypb11","doi-asserted-by":"crossref","unstructured":"R. W. Floyd,\n                      Algorithm97:Shortest path\n                      , Commun. ACM, 5 (1962), p. 345.","DOI":"10.1145\/367766.368168"},{"key":"atypb12","unstructured":"M. R. Garey and D. S. Johnson,\n                      Computers and Intractability: A Guide to the Theory of NP-Completeness\n                      , W. H. Freeman, New York, 1979."},{"key":"atypb13","doi-asserted-by":"crossref","unstructured":"M. C. Golumbic,\n                      Algorithmic Graph Theory and Perfect Graphs\n                      , 2nd ed., Ann. Discrete Math. 57, Elsevier, New York, 2004.","DOI":"10.1016\/S0167-5060(04)80051-7"},{"key":"atypb14","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2004.01.011"},{"key":"atypb15","first-page":"133","volume":"88","author":"Hadwiger H.","year":"1943","journal-title":"Vierteljschr. Naturforsch. Ges. Zu\u0308rich"},{"key":"atypb16","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-012-9670-2"},{"key":"atypb17","doi-asserted-by":"publisher","DOI":"10.1016\/j.disopt.2014.06.003"},{"key":"atypb18","doi-asserted-by":"crossref","unstructured":"D. Lokshtanov, N. Misra, and S. Saurabh,\n                      On the hardness of eliminating small induced subgraphs by contracting edges\n                      , in Proceedings of IPEC 2013, Lecture Notes in Comput. Sci. 8246, Springer, New York, 2013, pp. 243-254.","DOI":"10.1007\/978-3-319-03898-8_21"},{"key":"atypb19","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.1995.1006"},{"key":"atypb20","doi-asserted-by":"crossref","unstructured":"T. J. Schaefer,\n                      The complexity of satisfiability problems\n                      , in Proceedings of the 10th Annual ACM Symposium on Theory of Computing, San Diego, CA, 1978, pp. 216-226.","DOI":"10.1145\/800133.804350"},{"key":"atypb21","doi-asserted-by":"publisher","DOI":"10.1016\/S0166-218X(87)80003-3"},{"key":"atypb22","doi-asserted-by":"publisher","DOI":"10.1137\/0213035"},{"key":"atypb23","doi-asserted-by":"crossref","first-page":"681","DOI":"10.1145\/1132516.1132612","author":"Zuckerman D.","year":"2006","journal-title":"Proceedings of STOC"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/140975279","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T13:17:54Z","timestamp":1787318274000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/140975279"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,1]]},"references-count":23,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2015,1]]}},"alternative-id":["10.1137\/140975279"],"URL":"https:\/\/doi.org\/10.1137\/140975279","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,1]]}}}