{"entities":{"Q7017022":{"pageid":21605052,"ns":120,"title":"Item:Q7017022","lastrevid":77558843,"modified":"2026-05-06T09:30:01Z","type":"item","id":"Q7017022","labels":{"en":{"language":"en","value":"Reducing linear Hadwiger's conjecture to coloring small graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 8005009"}},"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":"Q7017022$154D13F9-19CA-4D08-BE7B-386D6B1B42D6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"18051e273e494c59bb69a20d1f2a8d9cf695d98b","datavalue":{"value":{"text":"Reducing linear Hadwiger's conjecture to coloring small graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q7017022$31BA8AE2-861B-42E1-AFA0-9CBB30A2ACAC","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"25b97d2dfa4492e451eb1a9139f8adae087a9f54","datavalue":{"value":"1560.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7017022$088789D0-0359-4B23-ADCC-AF3ACA3A3491","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"0103b1784f1aef4858c3e8008da7c32a4ab2397e","datavalue":{"value":"10.1090/JAMS/1047","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7017022$CFDE840C-C6A1-4F63-AF86-FFAB437D82E5","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"225e476b91ecf5346e6f0e17e96dd007c71cfacf","datavalue":{"value":{"entity-type":"item","numeric-id":299040,"id":"Q299040"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$2BFE015F-B2DC-4C02-BFEA-5232AEB5921C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"231702fbc5a30e710ffb4eed2c1114ae9b9221ef","datavalue":{"value":{"entity-type":"item","numeric-id":273166,"id":"Q273166"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$9A9C6DF0-C34C-4380-83CC-6C6A4C465D23","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"0739e5349975c4111ea4ec91f3592e78d78323f6","datavalue":{"value":{"entity-type":"item","numeric-id":2701699,"id":"Q2701699"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$D67FB9AE-CAE6-4F0C-B6B5-94027D7105D0","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"67e4ccb3c8e393f9241485303bf05c4583bf2cba","datavalue":{"value":{"time":"+2025-03-06T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q7017022$939A9AB4-2367-4323-87BF-2925B5BB321D","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"222a5460233641b7c1950d3d5181290f5f03a793","datavalue":{"value":"A graph \\(G\\) has an \\(H\\) minor if a graph isomorphic to a graph \\(H\\) can be obtained from a subgraph of \\(G\\) by contracting edges. The linear Hadwiger conjecture states that there exists a constant \\(C>0\\) such that for every integer \\(t\\ge1\\), every graph with no \\(K_t\\) minor is \\(C\\cdot t\\)-colorable. The main result of the present paper is \\N\\NTheorem 1.6: For any graph \\(G\\) with no \\(K_t\\) minor, and any integer \\(t\\ge3\\), there exists an integer \\(C=C_{1.6}\\ge1\\) such that, if \\(f_{1.6}(G,t)\\) denotes \\N\\[\\N\\max\\limits_{H\\subseteq G}\\left\\{\\frac{\\chi(H)}a:t\\ge a\\ge\\frac{t}{\\sqrt{\\ln t}},V(H)\\le C\\cdot a\\cdot (\\ln a)^4,H\\text{ is }K_a\\text{-minor-free}\\right\\}, \\N\\]\\Nthen \\(\\chi(G)\\le C\\cdot t\\cdot(1+f_{1.6}(G,t))\\).\\N\\NAs one corollary, the authors prove \\N\\NTheorem 1.5: Every graph with no \\(K_t\\) minor is \\(\\operatorname{O}(t\\ln\\ln t)\\)-colorable, which improves on Theorem 1.4 of [\\textit{S. Norin} et al., Adv. Math. 422, Article ID 109020, 23 p. (2023; Zbl 1512.05144)], which stated that for every \\(\\beta>\\frac14\\), every graph with no \\(K_t\\) minor is \\(\\operatorname{O}(t\\cdot(\\ln t)^\\beta)\\)-colorable. Other consequences of Theorem 1.6 are \\N\\NCorollary 1.7: There exists an integer \\(C=C_{1.7}\\ge1\\) such that the following holds: If for every integer \\(t\\ge3\\) we have that every \\(K_t\\)-minor-free graph \\(H\\) with at most \\(C\\cdot t\\cdot(\\ln t)^4\\) vertices satisfies \\(\\chi(H)\\le Ct\\), then for every integer \\(t\\ge3\\) we have that every \\(K_t\\)-minor-free graph \\(G\\) satisfies \\(\\chi(G)\\le C^2t\\).\\N\\NCorollary 1.8: There exists \\(C=C_{1.8}\\ge1\\) such that the following holds: Let \\(t\\ge3\\) be an integer. If \\(G\\) is a \\(K_t\\)-minor-free graph in which the largest complete subgraph has no more than \\(\\frac{\\sqrt{\\ln t}}{( \\ln\\ln t)^2}\\) vertices, then \\(\\chi(G)\\le Ct\\).\\N\\NCorollary 1.9: There exists \\(C=C_{1.9}\\ge1\\) such that for every integer \\(r\\ge3\\), there exists \\(t_r>0\\) such that for all integers \\(t\\ge t_r\\), every \\(K_r\\)-free \\(K_t\\)-minor-free graph is \\(C_t\\)-colorable.\\N\\NCorollary 1.10: For every integer \\(r\\ge3\\), there exists \\(C_r\\ge1\\) such that for all integers \\(t\\ge1\\), every \\(K_r\\)-free \\(K_t\\)-minor-free graph is \\(C_r\\cdot t\\)-colorable.\\N\\NThe authors also prove \\N\\NTheorem 2.3: There exists an integer \\(C=C_{2.3}\\ge1\\) such that the following holds: Let \\(t\\ge1\\) be a fixed integer. For every integer \\(k\\ge t\\), if \\(G=(V,E)\\) is a nonempty graph with density \\(\\frac{|E|}{|V|}\\ge C\\cdot k\\) and \\(G\\) contains no \\(K_t\\) minor, then \\(G\\) contains a non-empty \\(k\\)-connected subgraph \\(H\\) with at most \\(C^2\\cdot t\\cdot(\\ln t)^3\\) vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q7017022$4BDD4112-6A12-4AD9-80C0-1551462366A4","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"7d410aa128a8b8a63913c9594604f4ec3d0ad8b4","datavalue":{"value":{"entity-type":"item","numeric-id":590664,"id":"Q590664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$3BA9DE74-A066-4135-8F79-944373F174E3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7017022$3258459E-0FDA-4849-A79A-E0199057C7DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"49261cbbd2f3b64e072aca4630c2592536037a47","datavalue":{"value":"05C83","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7017022$28FF7B6F-0C81-4794-AEA9-F3493E97BC88","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3027552d8c2801b33eebbd9bf36c32dbb13776ed","datavalue":{"value":"8005009","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q7017022$3105BA96-E243-4807-8591-AF45DDE111FB","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"039109bc8d766890a2b24374a39b2d0059620204","datavalue":{"value":"Hadwiger conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q7017022$03D585E9-29AB-49C2-835C-C57CA5BE565A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9b96f8c8701e500d0edba5ad758e6118ad0eb646","datavalue":{"value":"linear Hadwiger conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q7017022$6F7D12E9-8A04-4C1E-B1B4-C4F8D984354B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e6d9ec77b0669b77734b6831d672122e99e5245c","datavalue":{"value":"minor","type":"string"},"datatype":"string"},"type":"statement","id":"Q7017022$1DB08A62-BFFF-4D05-85D1-D58232EEC728","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":"Q7017022$56D7A3E7-D36F-433C-BC76-B4D339BC9D91","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"20a3607138f204a5bcf712c32249c4a71485234e","datavalue":{"value":{"entity-type":"item","numeric-id":641195,"id":"Q641195"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$A1C77266-4F38-4F09-8725-45C9DF093F34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1f44a2befe28e4377da5341d92f1ad3ae9fffb8","datavalue":{"value":{"entity-type":"item","numeric-id":2563507,"id":"Q2563507"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$16C31B35-351F-4460-9D18-8BFD33C5949B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bcfb494419125416bb859bcd804f2f6c2ba431e0","datavalue":{"value":{"entity-type":"item","numeric-id":6074687,"id":"Q6074687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$20435814-44EA-4F8F-A5D1-8F78B52E964C","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":"Q7017022$46B652FF-EA4D-428B-9EFD-323E11FA4A2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ff211d4942c3444f76e1468280aec0751a49ac4","datavalue":{"value":{"entity-type":"item","numeric-id":2403691,"id":"Q2403691"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$8B536DCF-2507-4825-BB6A-C5A89DB9B8B5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"741f54f25393cf7ab7c6203b35b4eb489deb33ca","datavalue":{"value":{"entity-type":"item","numeric-id":6967249,"id":"Q6967249"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$B8E08843-5508-4C64-86E6-890025D60ED5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9611721eba427f286d4c509052f517b5821ce99d","datavalue":{"value":{"entity-type":"item","numeric-id":1053033,"id":"Q1053033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$71A2B8D4-9889-4408-99A3-EF23F9CE0709","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ddeecbf9d816b2aad50598d65bfe901077d0f337","datavalue":{"value":{"entity-type":"item","numeric-id":3013132,"id":"Q3013132"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$A9568D27-CDB4-41A6-90C5-D109944B0B05","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"80c999eb7e01550ee66dc976a3f6f0e042c6a261","datavalue":{"value":{"entity-type":"item","numeric-id":6133373,"id":"Q6133373"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$D39A25DC-7350-401B-A7E4-D6B862CDF9CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f9752745e0bf5079a46b3df4174fa00ba27470b0","datavalue":{"value":{"entity-type":"item","numeric-id":5837979,"id":"Q5837979"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$0D60DB45-6ECB-485F-BEBB-ECF4FCF9C0F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e8eebb9a54b3881ee0adeb153c28b0f131997cd4","datavalue":{"value":{"entity-type":"item","numeric-id":858685,"id":"Q858685"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$9E0760F6-A3D6-4AB9-ADB5-0E5C71C05575","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ba0ebf45e97073199b8ab81ace0c80bde2d0035","datavalue":{"value":{"entity-type":"item","numeric-id":878052,"id":"Q878052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$3370F840-22BE-46E3-8FB0-12969691B805","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2612faf0a43c0aefb5740277cd6c0a06dbbfa558","datavalue":{"value":{"entity-type":"item","numeric-id":3333070,"id":"Q3333070"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$354D974B-13AA-43DD-B6B5-B0BCB8C4E9D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c59623c60a6e1386539c0ef28bfc016f6933ca84","datavalue":{"value":{"entity-type":"item","numeric-id":760439,"id":"Q760439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$D1CCB221-3F6B-43E0-A461-99209F27D2FD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc9d0fb35664d596a28ec73c5cf6274eaa1b799b","datavalue":{"value":{"entity-type":"item","numeric-id":4800396,"id":"Q4800396"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$81AACC4E-C371-49EC-BAC1-F42EAAAB4EF2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"14911ef5c4e22b8eb6274f6843028021018c1c3a","datavalue":{"value":{"entity-type":"item","numeric-id":558314,"id":"Q558314"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$89BF44FA-F8B2-4F14-A16B-A7B37264C96E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"11bf152a68787f2a6ef185c4a8fb61f7416803d6","datavalue":{"value":{"entity-type":"item","numeric-id":2545698,"id":"Q2545698"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$5E6D7731-8B5F-43DA-89D1-1EB8F31C0A9A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"57c86e3e3fe8d91b005219aa08ae5fddff67ae58","datavalue":{"value":{"entity-type":"item","numeric-id":1445520,"id":"Q1445520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$1833FE26-91A6-4311-A075-51F4081B93A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f4bdab85ea6abb667b054a34d741cead315dd35e","datavalue":{"value":{"entity-type":"item","numeric-id":1633755,"id":"Q1633755"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$673CDBD0-EE4E-46F0-AB4A-8F6D149B467D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6794ae1e3a965ecde4ca687db497cb8cded32d43","datavalue":{"value":{"entity-type":"item","numeric-id":6141860,"id":"Q6141860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$B694D4CD-2F41-45F7-AD13-2067FF7AB72B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"96422ae25b301cd39fff2a80654d13f8da996f0a","datavalue":{"value":{"entity-type":"item","numeric-id":2099418,"id":"Q2099418"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$0C9AE50E-8888-46DF-A6AC-F8BBC98B594F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d0640c5b94e3d0480745735c4ecc238973ab703f","datavalue":{"value":{"entity-type":"item","numeric-id":2700634,"id":"Q2700634"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$272D6F54-6273-4703-B976-800BE8645CEC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7801a61c1b4ec810477af4a3768b4483d583cafc","datavalue":{"value":{"entity-type":"item","numeric-id":1569032,"id":"Q1569032"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$4BBD6CFE-57CE-4F79-BD0A-97F4F204F7A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"398ef8bc27e00efd8312d46a33efaa0333728c17","datavalue":{"value":{"entity-type":"item","numeric-id":1892832,"id":"Q1892832"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$D9E7E192-9D88-4ED4-8772-8912DE29F677","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"63b6b7209098b219a68d4d05c943181b0e1648e4","datavalue":{"value":{"entity-type":"item","numeric-id":2827298,"id":"Q2827298"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$2324B878-8903-45BB-B031-D7262574F692","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2fe07744ceca15792969573784ea9ff7a193f9c1","datavalue":{"value":{"entity-type":"item","numeric-id":1767622,"id":"Q1767622"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$881C6CF7-2EDD-4A4F-9CF2-3E752A088115","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b76156a4d5397786b7acde2677b3463186b48aa6","datavalue":{"value":{"entity-type":"item","numeric-id":3344229,"id":"Q3344229"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$02B490CE-3F64-4B61-991E-591A7F81A95C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"99dc09b8f4482f490f450bf5514d575a4967e820","datavalue":{"value":{"entity-type":"item","numeric-id":3506317,"id":"Q3506317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q7017022$9EAF735B-6B28-4A85-85D5-C847D3C673E3","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Reducing linear Hadwiger's conjecture to coloring small graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Reducing_linear_Hadwiger%27s_conjecture_to_coloring_small_graphs"}}}}}