{"entities":{"Q1348656":{"pageid":1359395,"ns":120,"title":"Item:Q1348656","lastrevid":68669466,"modified":"2026-04-13T01:18:59Z","type":"item","id":"Q1348656","labels":{"en":{"language":"en","value":"\\(n\\)-tuple coloring of planar graphs with large odd girth"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1740496"}},"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":"Q1348656$A5E08061-8881-4B78-9093-FC681003EAE5","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"e29881216565ccca8523b1b6520e83e0aaa23b22","datavalue":{"value":{"text":"\\(n\\)-tuple coloring of planar graphs with large odd girth","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1348656$A6481C0C-5A39-47FF-A91E-56F8ECA1D36E","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"51c66566806d2eb1c728d054d0dbbf3f57f930a8","datavalue":{"value":"0995.05053","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348656$CCCE01BA-9830-4D66-B09C-4A3A4D9EDA8C","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"511890414016001f87f67e677ff572f2fd1acbf6","datavalue":{"value":{"entity-type":"item","numeric-id":175515,"id":"Q175515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348656$22C2BF16-2DE1-480B-8014-60AA910233D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b0e5df302565d2de1eeef2fcdc9afdeee5289ecc","datavalue":{"value":{"entity-type":"item","numeric-id":335332,"id":"Q335332"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348656$4AE786CF-7423-4DB2-A98B-06F6ECFA25BF","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"62093226388c211ee4d5286124caf1fbc8b86437","datavalue":{"value":{"entity-type":"item","numeric-id":185060,"id":"Q185060"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348656$BB716359-3171-4A6C-B102-1C7367890507","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"05d02d494e311c112f365e2abe0dc31f2e442bf8","datavalue":{"value":{"time":"+2002-05-14T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1348656$1090BD54-0602-4E1F-8565-F78004B7218B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"a141f48c73edbb458ca0a5c6a25c9923e89c6b04","datavalue":{"value":"An \\((n,k)\\)-coloring of the graph \\(G\\) is a mapping \\(c:\\;V(G) \\to {\\mathcal{P}}_k(Z_n)\\) of the vertex set of \\(G\\) into the collection of all \\(k\\)-subsets of \\(Z_n = \\{0,1,\\dots ,n-1\\}\\) such that \\(c(u) \\cap c(v) = \\emptyset\\) if \\(uv \\in E(G)\\); alternatively, this coloring can be viewed as a homomorphism to the Kneser graph \\(G_k^n\\). The authors prove that every planar graph \\(G\\) with odd girth at least \\(10k-7\\;(k \\geq 2)\\) is \\((2k+1,k)\\)-colorable. Additionally, if \\(G\\) is a planar graph with maximum degree \\(\\Delta(G) \\leq 3\\) and girth at least \\(10k-9\\;(k \\geq 2)\\), then \\(G\\) is \\((2k+1,k)\\)-colorable. In the proof, the list of reducible configurations (with respect to \\((2k+1,k)\\)-coloring) is constructed; assuming a hypothetical counterexample, it is shown that it cannot contain any of those configurations. Then a calculation of Euler contributions of the counterexample contradicts its planarity.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348656$0B2FAF78-5D3F-478E-BF96-69742DC576C0","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"bf552a6496a70699f2802e7f7eff6309238b43f4","datavalue":{"value":{"entity-type":"item","numeric-id":383766,"id":"Q383766"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1348656$0579498E-DD62-4693-9D2F-80998C76DA22","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348656$51663571-B388-4C37-AA59-E55F768BFE6E","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c397a1ed212f3472bf2b44930fc5e1148ffd745b","datavalue":{"value":"1740496","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348656$122BF932-62E6-4F75-9156-056BDCAE9A29","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"8192f11610279d466bb99aa31056e9f91f415eb7","datavalue":{"value":"planar graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348656$91B3B3F8-0001-4093-A0E5-533D4F460146","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"55e8c2ab6cfecacf376282b0762944238412d916","datavalue":{"value":"odd girth","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348656$3E817B17-DFAF-4644-B33D-5C33ACDBDB95","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348656$BE622088-5899-4AEE-8C13-DA21CA7F6C66","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e308f8cd20f2b6dc60e2e7dcb2f90061e94de011","datavalue":{"value":"Kneser graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q1348656$0BC58AD5-10DB-4618-8FDD-C2039F83010E","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":"Q1348656$AAAA61D8-BC05-42B9-940C-FD6440F219A5","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"30c068fb7dbeed24db554676b1c262575fd0e512","datavalue":{"value":"https://doi.org/10.1007/s003730200007","type":"string"},"datatype":"url"},"type":"statement","id":"Q1348656$3B9907D1-D42B-4BAF-9739-8DC693AF9DC1","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"450f6edf5468967c8effc0b152512294ae2c1e73","datavalue":{"value":"W2067362800","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348656$EE37AD5A-1C14-45AF-9803-0B26C0970BE5","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"9e71bea5dffe4ab96bd3fe1b574895020910fa3a","datavalue":{"value":"10.1007/S003730200007","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1348656$CCD4FB1D-3067-4C6C-BD63-A3CD5364ADA9","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"28faf6fef104bed45fbd2fc09e7388b9796618e1","datavalue":{"value":{"entity-type":"item","numeric-id":5431618,"id":"Q5431618"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2d5c438e99a55b52bb4037944e2476c65c641ea8","datavalue":{"value":{"amount":"+0.8559678792953491","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":"Q1348656$7B81B6C7-619F-4BAC-9F44-FCEE65C742F7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6ecd83d04ece4fe7340ae2ce88c42c2fe02a7057","datavalue":{"value":{"entity-type":"item","numeric-id":3087093,"id":"Q3087093"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6cc49917d510f7af3185d630fce93a1a076e6181","datavalue":{"value":{"amount":"+0.838779628276825","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":"Q1348656$C956B347-D402-449A-9043-DC95575FF478","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c9d906f2fa2e6ac9ef0c043a884c224d32b1be88","datavalue":{"value":{"entity-type":"item","numeric-id":3109523,"id":"Q3109523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5949d7ad8cec765e9d3776840cf27c3967eacefe","datavalue":{"value":{"amount":"+0.8379371166229248","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":"Q1348656$F693BC01-13B4-48D7-A7C9-E3A5F9C32274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fffe2344d102861e0c02d1522918270e71c766cc","datavalue":{"value":{"entity-type":"item","numeric-id":625874,"id":"Q625874"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"190606938b30b7c3dee12e737b08747aa3fafb70","datavalue":{"value":{"amount":"+0.8165808320045471","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":"Q1348656$7503F8FC-501F-4A86-847F-C5F1D8E1DE7E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f3b510cd888ac3dc8004121ba7d13f8ef77918e1","datavalue":{"value":{"entity-type":"item","numeric-id":2329168,"id":"Q2329168"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"259a1ceffcf716f67537089233e8c3c97a423bed","datavalue":{"value":{"amount":"+0.7645946741104126","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":"Q1348656$12A90F41-747B-4C97-8DD8-05653FBB2232","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"\\(n\\)-tuple coloring of planar graphs with large odd girth","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/%5C(n%5C)-tuple_coloring_of_planar_graphs_with_large_odd_girth"}}}}}