{"entities":{"Q2565692":{"pageid":2576435,"ns":120,"title":"Item:Q2565692","lastrevid":44368467,"modified":"2025-11-22T09:29:10Z","type":"item","id":"Q2565692","labels":{"en":{"language":"en","value":"Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 2209140"}},"aliases":{},"claims":{"P31":[{"mainsnak":{"snaktype":"value","property":"P31","hash":"fd5912e4dab4b881a8eb0eb27e7893fef55176ad","datavalue":{"value":{"entity-type":"item","numeric-id":56887,"id":"Q56887"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$4AF03D32-8B7B-4CEB-AA95-195F74327EA3","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"1b01b4b2efda403a33851f19ef536ae38dca97b0","datavalue":{"value":{"text":"Improvements of the theorem of Duchet and Meyniel on Hadwiger's conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2565692$3EB700BB-A724-4AF9-876F-B3CAF682CFE1","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fa607b1337477b0544b665e7fd7c644d451d5dbc","datavalue":{"value":"1080.05074","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565692$3261D393-EC1D-4719-84B7-262F5C6B8FB4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"3f4e7bb5eb3d92423af4c11d1172a2aa89ed8c8c","datavalue":{"value":{"entity-type":"item","numeric-id":214979,"id":"Q214979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$B6764E8C-DBFF-44F8-ABFA-7456EA0D9E6A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"ea5a1d5841dde3ed27c188c8922256d04a1cf497","datavalue":{"value":{"entity-type":"item","numeric-id":189707,"id":"Q189707"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$BEDF36E2-69F8-4BFA-B490-35D839CF0029","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"9edef4e23817564b8500a1297f36d53756532a8d","datavalue":{"value":{"entity-type":"item","numeric-id":286762,"id":"Q286762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$D6C267BF-2408-4CBF-AC28-1E04AEDEDB38","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$A2874EFB-D82B-4C26-A7FE-FAD58842A87F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"149818fcb8bed0a5b750a95fd3a49925c0920292","datavalue":{"value":{"time":"+2005-09-28T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2565692$3E77A422-BBC9-4F2F-BF86-341E4D62DAD7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7b54b1e1668a40d44e2b34d3d7ee14dcd990cc71","datavalue":{"value":"The well-known Hadwiger's conjecture states that every graph \\(G\\) has the complete graph \\(K_{\\chi(G)}\\) as a minor where \\(\\chi(G)\\) denotes the chromatic number of \\(G\\). \\textit{D. R. Woodall} [J. Graph Theory 11, 197--204 (1987; Zbl 0672.05027)] conjectured that every graph \\(G\\) with \\(n\\geq 1\\) vertices has \\(K_{\\lceil \\frac{1}{\\alpha(G)}n\\rceil}\\) as a minor where \\(\\alpha(G)\\) denotes the independence number of \\(G\\). As \\(\\chi(G)\\alpha(G)\\geq n\\), Hadwiger's conjecture implies Woodall's conjecture. In case \\(\\alpha(G)=2\\), however, the two conjectures are equivalent [\\textit{M. D. Plummer, M. Stiebitz} and \\textit{B. Toft}, Discuss. Math., Graph Theory 23, 333-363 (2003; Zbl 1053.05052)]. In this context, a theorem of \\textit{P. Duchet} and \\textit{H. Meyniel} [Ann. Discrete Math. 13, 71--73 (1982; Zbl 0522.05060)] states that every graph \\(G\\) has a \\(K_{\\lceil \\frac{1}{2\\alpha(G)-1}n\\rceil}\\) as a minor. In this paper, the authors improve the theorem above as follows: (1) Every graph \\(G\\) with \\(n\\) vertices, clique number \\(w(G)\\) and independence number \\(\\alpha(G)\\geq 2\\) has \\(K_{\\lceil \\frac{1}{2\\alpha(G)-1}(n+\\omega(G))\\rceil}\\) as a minor, (2) Every graph \\(G\\) with \\(n\\) vertices and independence number \\(\\alpha(G)\\geq 3\\) has \\(K_{\\lceil \\frac{1}{(4\\alpha(G)-3)(2\\alpha(G)-1)}(n(4\\alpha(G)-2))\\rceil}\\) as a minor, and (3) Let \\(G\\) be a graph with \\(n\\) vertices and \\(\\alpha(G)=2\\). If \\(G\\) is \\((n-4)\\)-connected, then \\(G\\) has \\(K_{\\lceil \\frac{1}{2}n\\rceil}\\) as a minor.  For general graphs \\(G\\) with \\(\\alpha(G)=2\\), a problem due to Paul Seymour still remains open. It reads: Is it possible to obtain a larger constant than \\(\\frac{1}{3}\\) in the theorem of Duchet and Meyniel?","type":"string"},"datatype":"string"},"type":"statement","id":"Q2565692$0B955B11-B742-4317-AF78-7E9883E0BD5A","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c4d08f81dccf0def423a8aaa09abdd52c85c61ef","datavalue":{"value":{"entity-type":"item","numeric-id":185062,"id":"Q185062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$096FC983-004B-4C2C-8C6C-1168BF436D2C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565692$DFE76065-37FD-4C46-971C-0CF902C858E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565692$CB791EAE-26F4-477F-8CB1-A73093A5A333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565692$5249F5B2-9B7C-4BAB-80B3-830934E26FE3","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71d5fd3acd5f44fda1700dc63163d79e3c4eb4ee","datavalue":{"value":"2209140","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565692$5BE3A91B-F6AD-403B-9881-83091FB66BD0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q2565692$DC121440-B6DE-400E-AC65-EF0E6B410BCE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8123646fa06d72653de6faafa57ea821e244015f","datavalue":{"value":"connected matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q2565692$1B06EA0F-7FFD-4F78-8507-9B088321F25E","rank":"normal"}],"P1460":[{"mainsnak":{"snaktype":"value","property":"P1460","hash":"57f7fea50d2ce1b39b695c4a1313582eed405e38","datavalue":{"value":{"entity-type":"item","numeric-id":5976449,"id":"Q5976449"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$22B0380D-3FC4-49A6-A894-BCF09F80A30A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"30ab4040682cbe39623511978ce6c27fdaf8c04a","datavalue":{"value":"https://doi.org/10.1016/j.jctb.2005.04.001","type":"string"},"datatype":"url"},"type":"statement","id":"Q2565692$37A60706-1BE2-40F7-9DE1-4DD10DD43C5F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a27e86089614fed45cbdb787aa910f4b05263de4","datavalue":{"value":"W2050035467","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565692$C5939CC1-652B-4ADF-B592-C07DB12C16D1","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"759d93a42f19b25cb0989594bce810f7d355913b","datavalue":{"value":{"entity-type":"item","numeric-id":4414635,"id":"Q4414635"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$41BAAEA8-2491-4B83-84B1-04A3FE0A40CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"28d8eafc9a79890029b73b9b2b2eaf564379e3a8","datavalue":{"value":{"entity-type":"item","numeric-id":3672036,"id":"Q3672036"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$D658348B-E556-4622-8979-725A88FFD9E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$FE876DF3-3129-46B9-9247-45632050D158","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"15132b3e75729a6d081fd45a4b035add2a9fce88","datavalue":{"value":{"entity-type":"item","numeric-id":4851927,"id":"Q4851927"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$2017222A-42A0-4A7B-86EC-1312EFA4B109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4baabbf3a88325529b40376d9838b574a897fb04","datavalue":{"value":{"entity-type":"item","numeric-id":1092928,"id":"Q1092928"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$A94BAE2F-B7ED-4B3D-B37E-572867D32E13","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"dbaabdff0ad573ac959e2110120e9232308d5ad8","datavalue":{"value":{"entity-type":"item","numeric-id":4823312,"id":"Q4823312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$CA33240A-5CA6-45BC-8E0F-9C74B07D4859","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3e36480d211254ed0fdcf49a2ad1e6b170e2c24d","datavalue":{"value":{"entity-type":"item","numeric-id":3824327,"id":"Q3824327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2565692$DA0F10C5-7283-4D07-A87B-5D478A89DF5A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d41e14404887d274f6fbf546ac482b9f0f0a7db3","datavalue":{"value":"10.1016/J.JCTB.2005.04.001","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2565692$D44512BC-85C2-448F-9540-973486842D17","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eda8731c1ed7fae95b35a703497d124c04cb6e70","datavalue":{"value":{"entity-type":"item","numeric-id":641195,"id":"Q641195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b24e245dd2dea5b00dcd768c96bc754c92cb5cf","datavalue":{"value":{"amount":"+0.8776726","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$6E56C0B9-23B8-4F2E-8820-15368C13873A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7905039f3823b14b20d878308c4fcf608fe1d1d6","datavalue":{"value":{"entity-type":"item","numeric-id":5348213,"id":"Q5348213"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"efe744a282517573f023307cd306b4c8e86b0064","datavalue":{"value":{"amount":"+0.85073996","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$232A7AF1-A098-4FA6-8384-9CE2981A66F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1ba15bc6ed4188aa46046617b70b01f07893dbdd","datavalue":{"value":{"entity-type":"item","numeric-id":5434255,"id":"Q5434255"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3891bf90700d2247594b4957cf6ee8c73d765dc1","datavalue":{"value":{"amount":"+0.8387547","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$31F61C51-DBEB-41B6-B6AB-3E2C6C86C25D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b42d162e53b8076aa56e9c28bac311fa8fdd4170","datavalue":{"value":{"entity-type":"item","numeric-id":3013132,"id":"Q3013132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1d901ec73719aa3f2554836cc99a536ff3a6a76b","datavalue":{"value":{"amount":"+0.8384947","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$B0793E91-2837-43F3-B3B5-74C40FD35E67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7a7717aea62c9c705ff26c8ad11f3909714c4cf","datavalue":{"value":{"entity-type":"item","numeric-id":3634209,"id":"Q3634209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"928e731aa7bdb9536433e9cb9c6e8d69b4d0dba3","datavalue":{"value":{"amount":"+0.8346244","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$89FB11D0-695D-470D-ADCE-9B9D9C389F96","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b82287f42be4ab0529c3bcb1288ecf736a06baac","datavalue":{"value":{"entity-type":"item","numeric-id":858685,"id":"Q858685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c39a9fa9b9facbce11b31c80d6015c8b4d460c93","datavalue":{"value":{"amount":"+0.8130982","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$9007432C-D516-4A1F-8178-9DACB00333F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a181986d63478ae5ca1253f0d5afadbc20592641","datavalue":{"value":{"entity-type":"item","numeric-id":5387693,"id":"Q5387693"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"934f7167814b2f193902d895920f7b37c5f0acab","datavalue":{"value":{"amount":"+0.80373836","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$428A08F1-B839-4822-85B6-64741C7AE5B3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0ae6f0c2f8bf415d0ddfb68493fadf0efa0818b3","datavalue":{"value":{"entity-type":"item","numeric-id":3824327,"id":"Q3824327"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"821362da74e08625be18b776cda6479a9e5ff272","datavalue":{"value":{"amount":"+0.7920845","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$20FD8565-E1BE-40D1-AD39-A31D4EB128E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a01fb29d5305c7ff9d82c271696cd443f8716bc2","datavalue":{"value":{"entity-type":"item","numeric-id":5272642,"id":"Q5272642"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"21fd2da44d9e353265088298d451692c55612637","datavalue":{"value":{"amount":"+0.7883985","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$B00A07ED-DBB7-452A-B2FF-9343EB70AB7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"39e23aa4d8ef31ebdbf5c3995a51cf1e63a2fe35","datavalue":{"value":{"entity-type":"item","numeric-id":3553232,"id":"Q3553232"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d7abec41980b9e67e67e54af806feb4dba1a8b23","datavalue":{"value":{"amount":"+0.7869327","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2565692$4EABB3C5-91F7-4304-8269-F4C18FAEFE19","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2565692","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2565692"}}}}}