{"entities":{"Q1322020":{"pageid":1332770,"ns":120,"title":"Item:Q1322020","lastrevid":46315707,"modified":"2025-12-24T13:33:14Z","type":"item","id":"Q1322020","labels":{"en":{"language":"en","value":"Coloring graphs without short non-bounding cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 562408"}},"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":"Q1322020$1940434D-3098-43CC-8AC9-9F72D9C71743","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"97592534abe5f1a06b9960beb0b2d00cc7501b27","datavalue":{"value":{"text":"Coloring graphs without short non-bounding cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1322020$0D7F85AF-4792-4A21-87A7-6504B5164B4F","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"f9f73648cf39bb19a61b1aa3d2f3039c4cb28dd4","datavalue":{"value":"0793.05058","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322020$67B2789A-4E74-4BCA-8589-B4144DE1D5D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"f264bee44e3260fb9fc7cdfc769e09b929db5c43","datavalue":{"value":{"entity-type":"item","numeric-id":1140665,"id":"Q1140665"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322020$ECCD33E2-549F-43A0-AECA-9042AE67B004","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"96650f014ad2d7966e931e79230c3a74fac9c2f8","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322020$B0766AFB-2226-48AD-8E74-C672B3165A7E","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":"Q1322020$FC994001-21E9-4B74-8E0F-2619F471847C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"fbc2ac0030a794298a44d66dd84da3932fc8da2c","datavalue":{"value":{"time":"+1994-08-10T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1322020$DF65D6C7-176E-4BAC-BC87-D6BE5EA1E730","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"773eb8add9b1303593e0f4dd2093823bf82bb6db","datavalue":{"value":"It is shown that there is a constant \\(c\\) such that if \\(G\\) is a graph embedded in a surface of genus \\(g\\) (either orientable or non-orientable) and the length of a shortest non-bounding cycle of \\(G\\) is at least \\(c\\log(g+1)\\), then \\(G\\) is 6-colorable. The same condition together with the additional assumption that the girth of \\(G\\) is at least 4 (respectively, 6) guarantees that \\(G\\) can be 4-colored (respectively, 3- colored). The fact that the proofs use nothing but elementary techniques sheds some new light on the problem of coloring graphs on surfaces. These results improve and generalize results obtained by Cook [\\textit{R. J. Cook}, Chromatic number and girth, Period. Math. Hungar. 6, 103-107 (1975; Zbl 0313.05107)], Woodburn [\\textit{R. L. Woodburn}, A 4-color theorem for the Klein bottle, Discrete Math. 76, No. 3, 271-276 (1989; Zbl 0685.05019)], and some other people. The results also complement a recent outcome of Thomassen who proved a five color theorem of the same type under stronger hypotheses.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322020$7102C998-1609-4FED-A6D7-4E7CE22E9064","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322020$7D458CA2-DBF1-41E4-B823-89A3E3F571B1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322020$0BDC919A-4874-40BD-98B8-B79DCE682D7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322020$59952E83-FD16-4BA0-8DE2-43BE4788164B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5bb1e2603fa50f7ad2e180d19705c8966a990c0","datavalue":{"value":"562408","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322020$7BB11BC3-5D88-45C5-B3B0-A9D463C315DD","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322020$45A58BE5-A0F8-4C15-8E53-02F58669A2D7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2efb8ac6da67b5c7613666bc2ec072e59cc1d046","datavalue":{"value":"locally planar graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322020$A2B35F8A-EAC7-425E-9415-94016F98BE70","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7404f15c5e0c999131d68dad55a7c6f7a00faaef","datavalue":{"value":"map coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322020$2B8C180C-1D18-4CDA-81E2-E8561B09BE03","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322020$052581EE-3CCD-49F6-AC3C-9E82833D9D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"be003d48cba8b6de8409c66fbe9f6c5c7da92cd0","datavalue":{"value":"coloring graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322020$15C6B5B1-3144-42E1-BB9B-CE527ACC5891","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"82e10b106979077ac626034ec385c48041ecfb89","datavalue":{"value":"surfaces","type":"string"},"datatype":"string"},"type":"statement","id":"Q1322020$249A940A-6690-4D4E-ABE7-7D1E23F31A91","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"abf255b967b94e917e05e1834cde56652b9b0e09","datavalue":{"value":{"entity-type":"item","numeric-id":181823,"id":"Q181823"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1322020$04C4050E-93AA-45D2-89AC-E1F63A18C0E5","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":"Q1322020$5E065A8F-CE0B-44FF-B14A-94D32A6D5C42","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"cbe7bf09e812b26891841eeaa0f5c7fc6822943d","datavalue":{"value":"https://doi.org/10.1006/jctb.1994.1018","type":"string"},"datatype":"url"},"type":"statement","id":"Q1322020$2C07D708-FABC-4C3C-990B-03B90E59DEF2","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e0581931cc3c275b3e51d587b72ae2f1833b2835","datavalue":{"value":"W1980277139","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322020$8BDE9391-F82E-4D6D-AD88-0D0FE7C2764F","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8b2055a06d8b2b318df27036ad5c54eaee03aeb7","datavalue":{"value":"10.1006/JCTB.1994.1018","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1322020$F7F8C4A5-2BC0-41E4-A9D0-86A71EFB919E","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7dd5caa19517af8fcd9654dd3d746f1b1607ff0b","datavalue":{"value":{"entity-type":"item","numeric-id":4372592,"id":"Q4372592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d356606b9aa787e23eccf0883f4a85f5bf30bf6d","datavalue":{"value":{"amount":"+0.8310614228248596","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":"Q1322020$BD90812A-5E0F-4578-A522-878AA09DBF3F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bb363148ab83f1d0ab9485d3607195f225ffbecd","datavalue":{"value":{"entity-type":"item","numeric-id":4560169,"id":"Q4560169"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9ba9049ee733c4215b42dce0ba4fa4a78e5950bf","datavalue":{"value":{"amount":"+0.8293486833572388","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":"Q1322020$A42258C5-BD2D-4B9F-AE4F-47B0BAB8CAC1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"dd8120b5afd334b74554232709c3c2af9573ee63","datavalue":{"value":{"entity-type":"item","numeric-id":1898734,"id":"Q1898734"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e9b1c2f69d7677ce5c83f84e1a59e6ad7985d393","datavalue":{"value":{"amount":"+0.8223187923431396","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":"Q1322020$E899C79D-41D0-4A5C-965F-C774308191DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d48dcf34a57c539eaad554dbc8ce41e5ea412f4","datavalue":{"value":{"entity-type":"item","numeric-id":2822588,"id":"Q2822588"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43732751a51be0a4670d3dc17ecfee4161013465","datavalue":{"value":{"amount":"+0.8143502473831177","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":"Q1322020$71AF9071-DD0B-4BD3-9C88-EAA974B82B82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f7d8bd3c69edf40b8afb8f57b337b04f1ac0a74d","datavalue":{"value":{"entity-type":"item","numeric-id":3824328,"id":"Q3824328"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"050bbb1b893052015e8c569d84b94baceb164629","datavalue":{"value":{"amount":"+0.8115206360816956","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":"Q1322020$21E2ECDB-AA84-46A5-8514-6922A441E713","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1322020","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1322020"}}}}}