{"entities":{"Q698612":{"pageid":700461,"ns":120,"title":"Item:Q698612","lastrevid":63606300,"modified":"2026-04-11T14:18:03Z","type":"item","id":"Q698612","labels":{"en":{"language":"en","value":"Graph color extensions: When Hadwiger's conjecture and embeddings help"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1803674"}},"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":"Q698612$9794EFB0-5DBC-4531-B1E1-BCA957F54BA6","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"eade04820fbbe679dffbe5a79072b54f1257a07c","datavalue":{"value":{"text":"Graph color extensions: When Hadwiger's conjecture and embeddings help","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q698612$6ADC460F-8E60-4C39-B2D4-B8C4F43314BF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"24d08d9314fc17e6f01698a4e6a1b66544919f3c","datavalue":{"value":"1005.05017","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q698612$93F98ED7-69D3-4221-9276-7A4FCD60BE6F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"82040cfe7ba0d41798d213a2940864deca0691a1","datavalue":{"value":{"entity-type":"item","numeric-id":186192,"id":"Q186192"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q698612$2681F38A-85D3-4B89-A063-AE29FE94E39E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f65a464c681eb2ee7fe919c3548aecc7a06fc312","datavalue":{"value":{"entity-type":"item","numeric-id":536233,"id":"Q536233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q698612$8E0A22DA-0907-42F0-8216-B526611506F9","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"ebc7441ecfd9ecfa38d48ddc4b2adb39ac7d7000","datavalue":{"value":{"entity-type":"item","numeric-id":161296,"id":"Q161296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q698612$E9B1E429-D2C2-49BE-A3D9-AAA7EA113D58","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a2e0fdb3e4c16d994bf6f5d504c6aa80c971ee86","datavalue":{"value":{"time":"+2002-09-22T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q698612$2B62B1DC-4085-461C-A183-E51C96DAFF14","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"352d1e2e4220509e4fdd0263d681be62f196d500","datavalue":{"value":"https://eudml.org/doc/122366","type":"string"},"datatype":"url"},"type":"statement","id":"Q698612$EA9D79A0-8888-44D8-BD08-D8CE82BA9E80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"09d7a1871d297e4b331bf53ce0ffa07e68a65888","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_9/Abstracts/v9i1r37.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q698612$E52C2765-FB52-4B1C-A432-AC603E3584AB","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"4b4d83d1a8311bf27d347284d99b6a6828638f02","datavalue":{"value":"Summary: Suppose \\(G\\) is \\(r\\)-colorable and \\(P \\subseteq V(G)\\) is such that the components of \\(G[P]\\) are far apart. We show that any \\((r+s)\\)-coloring of \\(G[P]\\) in which each component is \\(s\\)-colored extends to an \\((r+s)\\)-coloring of \\(G\\). If \\(G\\) does not contract to \\(K_5\\) or is planar and \\(s \\geq 2\\), then any \\((r+s-1)\\)-coloring of \\(P\\) in which each component is \\(s\\)-colored extends to an \\((r+s-1)\\)-coloring of \\(G\\). This result uses the four color theorem and its equivalence to Hadwiger's conjecture for \\(k = 5\\). For \\(s=2\\) this provides an affirmative answer to a question of Thomassen. Similar results hold for coloring arbitrary graphs embedded in both orientable and non-orientable surfaces.","type":"string"},"datatype":"string"},"type":"statement","id":"Q698612$20ECE32F-20B9-4646-B04D-4DA83971BD91","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q698612$7EFC23EC-505A-41E5-8388-844B8089B2A9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q698612$2E7C8E63-B358-435F-B857-BC5E61A7DCA6","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"cd24f88460903441eb9dcbf19c20f223323e6478","datavalue":{"value":"1803674","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q698612$9B70DDBD-785D-40C7-960B-F126832C3222","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":"Q698612$67699274-3AE8-4D87-AF49-A25591D98D41","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"798a5f18bb21fb85754d6efabc34cad872769246","datavalue":{"value":"bafkreidoypmecozljeuwhg44a226k3ytsjomcoccazok5xdfuloop747eu","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q698612$3936A5E3-21C4-485A-A9CB-848CED081210","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9a9629afe195f716495bb95598c76829631e8074","datavalue":{"value":{"entity-type":"item","numeric-id":1034219,"id":"Q1034219"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0f402306d0f79b1a16a8f5e4722d616c5c8a44a6","datavalue":{"value":{"amount":"+0.9069146","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$1BF38958-6232-45AB-8AEA-B2A90CD34470","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ee1bc4e1e2cce9db911c2da25ffd4a2a926b16aa","datavalue":{"value":{"entity-type":"item","numeric-id":1569052,"id":"Q1569052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0dee448816baa9639ff213a4548ebc7c31f04a41","datavalue":{"value":{"amount":"+0.9018584","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$003F8C59-FD9E-433C-A661-442805C9EC12","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d339bd2243514e67ac573eb548436f5022a74f38","datavalue":{"value":{"entity-type":"item","numeric-id":1584287,"id":"Q1584287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a12fdbe0743657b71f9d24e50a58ffdc42d30401","datavalue":{"value":{"amount":"+0.8963276","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$C056E643-E2B0-473E-8455-D3567A452D4D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cbf12613ecae666e04123aa7fa2c80753585a01b","datavalue":{"value":{"entity-type":"item","numeric-id":4071274,"id":"Q4071274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fddd5fe6e7afb69969471574358d22b08eaa16b2","datavalue":{"value":{"amount":"+0.8958368","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$2E618BD7-75FC-431D-8205-8344BA6C206B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1496d9ea1de31468bbd158bbd3d631f476d5133c","datavalue":{"value":{"entity-type":"item","numeric-id":1586769,"id":"Q1586769"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"09d7bba07383cd118cf9d4d7a6f38c060e1fcb6c","datavalue":{"value":{"amount":"+0.8956008","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$779C3E4F-9673-4EEA-9A53-53FED6F287DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"22cd26cab360e716cc2bbbae6457e142b6817925","datavalue":{"value":{"entity-type":"item","numeric-id":1567669,"id":"Q1567669"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3cb8cd35dc767a01f4d1a050e8e5f9c713bbea8f","datavalue":{"value":{"amount":"+0.8944898","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$CAD493EE-5ABC-46E9-83D7-81682992FE50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"df7cfe06708d03e69ec3385d19f04e3f40f12a02","datavalue":{"value":{"entity-type":"item","numeric-id":2301555,"id":"Q2301555"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"619c825d098852cce7b60d7b6b4038ab6765d951","datavalue":{"value":{"amount":"+0.89342904","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$64EF1A60-B900-4A12-829E-02DE7CBA4993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"162881ea3b04a9500b466142737d37b493f16679","datavalue":{"value":{"entity-type":"item","numeric-id":5241164,"id":"Q5241164"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"704e592abf20cb94e44aefad52d5aa29c42539f2","datavalue":{"value":{"amount":"+0.8927219","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$52E0B05E-3AA8-49C2-A59D-37BCCE6888B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"eae112f0ba3fdc666a9d9f466bf913083758c944","datavalue":{"value":{"entity-type":"item","numeric-id":4668721,"id":"Q4668721"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e3b1efae259d05bb3b15427126e4456e1b76991","datavalue":{"value":{"amount":"+0.8909884","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$42E4B62C-D1A1-4CE4-8743-7DA15F105B1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c05bc3dbca616521508c59e79a2790b9582e02a8","datavalue":{"value":{"entity-type":"item","numeric-id":1576578,"id":"Q1576578"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0cc740eaed6dd6ae066942b718f42166c4a0a2fb","datavalue":{"value":{"amount":"+0.8900153","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q698612$B3A315FA-7633-4AD6-8206-FC8875188771","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Graph color extensions: When Hadwiger's conjecture and embeddings help","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Graph_color_extensions:_When_Hadwiger%27s_conjecture_and_embeddings_help"}}}}}