{"entities":{"Q1349093":{"pageid":1359832,"ns":120,"title":"Item:Q1349093","lastrevid":70214508,"modified":"2026-04-13T13:12:58Z","type":"item","id":"Q1349093","labels":{"en":{"language":"en","value":"Matchings and Hadwiger's conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1743026"}},"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":"Q1349093$1193CA39-1F3A-4708-8DF3-A6782E8D5538","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"da79b32db3fb2505a565d56c148989cf4fe51941","datavalue":{"value":{"text":"Matchings and Hadwiger's conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1349093$DDA3EC18-CF87-404E-BF2E-FB161560088F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"b91f40920ef0f19a1b5eb1a50baa6f733eff3e74","datavalue":{"value":"0995.05115","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349093$28E733C3-EDF5-4C16-9872-00C00BF13CD9","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"f45836db26b3a712bbe53f369d8a9ce398c7ea49","datavalue":{"value":"10.1016/S0012-365X(01)00087-5","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349093$5FCD8AAA-6B37-4E5A-B894-818C5D6294FF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349093$FCFE379C-6910-4038-907E-6BC2D24BCCF1","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"cda08edf6e14c28a948f9b78f5bc4351bb49e6b0","datavalue":{"value":{"time":"+2002-05-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1349093$22671066-C74E-44BF-A0A7-D55AC54A23A0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"41a3a38052a955beefd661ee212990afbf71c205","datavalue":{"value":"Hadwiger's conjecture says that every graph of chromatic number \\(k\\) contains a \\(K_k\\)-minor. Although verified for \\(k\\leq 6\\) so far, in general it still remains open. Suppose that graph \\(G\\) on \\(n\\) vertices is the only counterexample to the conjecture among its induced subgraphs and investigate the properties of its complement \\(H\\). The main results of this article are that then \\(H\\) contains a matching of size \\(\\lfloor n/2\\rfloor\\), is a subdivision of a 3-connected graph and has tree width at least 4. It is also observed that the same results are true for Colin de Verdi\u00e8re's conjecture \\(\\chi(G)\\leq\\mu(G)+1\\) introduced in [J. Comb. Theory, Ser. B 50, 11-21 (1990; Zbl 0742.05061)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349093$B6080518-EF35-4531-98D9-BF14C8B3C4DB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"c0617d45f23e5dfc7fb0eb4ddcab2f46301293e8","datavalue":{"value":{"entity-type":"item","numeric-id":414470,"id":"Q414470"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349093$03D5BF24-68F4-4DAD-A276-C7832D5FB090","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349093$B051A99B-92D8-4E3E-9A5E-846BBDB4D963","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349093$00AEF3D5-9F29-4075-99BA-66E8811541C5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"1bb0d3e5e35385c914cd1cf5d6acf2292d4a8fc6","datavalue":{"value":"1743026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349093$D49B5476-0FFD-4FAB-B993-BF3370FC8810","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdefb28951ee63f397ce9368bae3e97a2589921e","datavalue":{"value":"Hadwiger's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349093$172D7377-9E00-4189-AA4F-732FBF0A8B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bcc771f9c4cbb132a4fb9368403bb895cba44b70","datavalue":{"value":"matching","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349093$23C162C7-77D1-46EC-A42E-5C3DE70FF549","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b17e6e28d1a18f7a35b77cc1e7558e6f62021227","datavalue":{"value":"tree width","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349093$8DC9D8D6-AA55-4E4D-8A2F-CE9FBD342C59","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0cf3225dac24af3251c3a9dae1c11f09692a6f46","datavalue":{"value":"Colin de Verdi\u00e8re's conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q1349093$36ECEFA7-A118-4865-9483-4AD7D20B108B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a58b3a5be3b06a056c2a02a0f20493f73a30ac94","datavalue":{"value":{"entity-type":"item","numeric-id":765199,"id":"Q765199"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1349093$4C80D4AC-1D17-43EE-9C7D-2F48A8F64652","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":"Q1349093$5D2EEB62-CB4E-441B-B74C-F989D8D0F001","rank":"normal"}],"P12":[{"mainsnak":{"snaktype":"value","property":"P12","hash":"f27cf55a42ed2a91c79f1b6970aedf46fb4b41bc","datavalue":{"value":"Q123122690","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349093$A7CA390C-E90A-451E-83D0-2CD1E7877BE2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ae4fe5101511a1b5f31e0e028500765a27c23d65","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(01)00087-5","type":"string"},"datatype":"url"},"type":"statement","id":"Q1349093$96E12BF3-AC3A-4C3B-9D26-549310CDDE75","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"33dbb8ca6d22310b35daadbe5ee26c4aa5b4c581","datavalue":{"value":"W2082273239","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1349093$FCE93CD7-A739-49A9-AB44-A1F72EDE9095","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fa4faa941c8402f79111797025e7bdaf56abf01","datavalue":{"value":{"entity-type":"item","numeric-id":4823312,"id":"Q4823312"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"403e4c9a5ed88ed93a9cb51721a299aa539d15e9","datavalue":{"value":{"amount":"+0.859794020652771","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1349093$5E6EA7ED-0323-4D2B-A435-B11527817C36","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45574b1fb0bb29d4fbdfd958c31a2b854ebbbf29","datavalue":{"value":{"entity-type":"item","numeric-id":2958193,"id":"Q2958193"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cfdfe16caee123e229a24b441c2b862a68ec62de","datavalue":{"value":{"amount":"+0.8569689393043518","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1349093$55C792C2-2A82-4CC2-A95E-202E31009BDB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"94187eea7ac9ebdde9b8d69651804f7b6024e0d4","datavalue":{"value":{"entity-type":"item","numeric-id":1311018,"id":"Q1311018"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6d2dc11a20ff995758dfe7233a49bb9a481a2e4b","datavalue":{"value":{"amount":"+0.8351305723190308","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1349093$C8A422B0-44FF-41EE-A5BA-142132C85109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8065d2d06d8fc6852de00e4dcdd0bd89e80c2c05","datavalue":{"value":{"entity-type":"item","numeric-id":2822591,"id":"Q2822591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0135967c173cbe900ca5b83d9a74bc96e9e23065","datavalue":{"value":{"amount":"+0.833273708820343","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1349093$2F6A5BA0-A26E-403D-A1B1-3BA4D98C04FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fdfe54c27f09131c53a174448ccbe3a99b0fc6b5","datavalue":{"value":{"entity-type":"item","numeric-id":2384811,"id":"Q2384811"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ac1f27b58c77e3878aab30aec8e37325e2a8b603","datavalue":{"value":{"amount":"+0.8326774835586548","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"a327a09ea0305e98d5cf33bd4036320e19f2aed0","datavalue":{"value":{"entity-type":"item","numeric-id":6821328,"id":"Q6821328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q1349093$CDADE317-328F-462F-9D34-0C7BD9D8C24C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Matchings and Hadwiger's conjecture","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Matchings_and_Hadwiger%27s_conjecture"}}}}}