{"entities":{"Q2668022":{"pageid":2678765,"ns":120,"title":"Item:Q2668022","lastrevid":57993837,"modified":"2026-04-03T09:20:18Z","type":"item","id":"Q2668022","labels":{"en":{"language":"en","value":"Characterization of 4-critical triangle-free toroidal graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7483276"}},"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":"Q2668022$ECF27D77-F68F-4073-B1AB-C3A5018BD41F","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"10089d0c503a8d2ef36993849ad3d234e283dcbc","datavalue":{"value":{"text":"Characterization of 4-critical triangle-free toroidal graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2668022$9B94D57C-7D26-44B3-94B1-2D6E99155AFE","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"29fb071e571d6172f659d7ebb499d98e9d495940","datavalue":{"value":"1484.05067","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$9F59A680-512B-4251-B3A8-1D4890460B16","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"0344539925c30eafc8102699adfab87d48c82922","datavalue":{"value":{"entity-type":"item","numeric-id":213911,"id":"Q213911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$0E42D2E6-DC9F-4F1F-ACF3-2BCBB47F0FC0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a65324484aae7c7705437c9bb8dfa9ed652f4cab","datavalue":{"value":{"entity-type":"item","numeric-id":1642704,"id":"Q1642704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$A6F4DF88-C4A9-4A7B-A613-F4F8CAE5A3CF","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":"Q2668022$3EC42772-F34C-4C92-9B43-9B9A6E5E6B54","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"2199ecf1fe17346ff9ea48622eb6ad7ecdd5bf0e","datavalue":{"value":{"time":"+2022-03-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2668022$E332C96F-3A0A-41BC-9738-4949EE99DC5F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"ee5a919e8511c376218f1a0254d4791055383859","datavalue":{"value":"https://arxiv.org/abs/2009.00864","type":"string"},"datatype":"url"},"type":"statement","id":"Q2668022$AC9BCF3F-8B7D-4327-BB3C-0ED9C13AEFAF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"c6bfd8f39212b846ad16cfd9bb4cd6599b1c2bae","datavalue":{"value":"A well-known theorem of Gr\u00f6tzsch states that every planar triangle-free graph is 3-colourable. However on other surfaces this is not true; \\textit{J. Gimbel} and \\textit{C. Thomassen} [Trans. Am. Math. Soc. 349, No. 11, 4555--4564 (1997; Zbl 0884.05039)] showed that triangle-free graphs on the projective plane are 3-colourable if and only if they do not have a bipartite quadrangulation as a subgraph.  The paper under review considers the triangle-free graphs on the torus which are not 3-colourable. Since a graph is \\(c\\)-colourable if and only if does not contain a \\((c+1)\\)-critical subgraph, it is sufficient to describe the \\((c+1)\\)-critical subgraphs. The main result of the paper is an exact description of 4-critical triangle-free toroidal graphs. There are infinitely many of them, but they can all be obtained by triangulating faces of 186 template graphs.  In a bit more detail, say a simple template \\(T\\) is a graph \\(G_{T}\\) 2-cell embedded in the torus together with a subset of its even-length faces. A graph drawn in the torus is represented by the simple template \\(T\\) if a graph homeomorphic to \\(G\\) is obtained by filling each face of \\(T\\) by an arbitrary triangulation. Then the detailed result is that there is a set \\(\\mathcal{T}\\) of 186 simple templates with the properties that every 4-critical triangle-free graph drawn in the torus is represented by one of the simple templates in \\(\\mathcal{T}\\) and no graph represented by a simple template in \\(\\mathcal{T}\\) is 3-colourable.  Recalling that the edge-width of a graph drawn in a surface is the length of its shortest non-contractible cycle, the result implies (for example) that every triangle-free graph drawn in the torus of edge-width at least six is 3-colourable. This has implications for algorithms to 3-colour triangle-free toroidal graphs where possible.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668022$4DA8D2B9-0361-4F2B-A222-7D01A64445BD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$A5925209-EEA6-4F81-89BB-5949902A5AA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"357c7c34a1a90d83243f17011b7aa90788d1792d","datavalue":{"value":"05C10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$7E1EB290-D6A6-4E3F-B7B0-460A32330657","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$3485D56D-93E6-4E3E-9E07-9F4A5D3EF272","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"2fd5ba61c492f09082ae88370fa92e256be14e94","datavalue":{"value":"05C75","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$ADCD5C9F-7CF2-4BB2-8CC9-9030F1B3DD9A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"048b22d8000af16873d23f9e48d5c40f4aa7634c","datavalue":{"value":"7483276","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$8D5E3FBA-9819-4D17-A5D1-49003DA4FBC2","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b999a30face15aad7449f079f4627b1e5e0eb2bc","datavalue":{"value":"coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668022$0BD0B586-F137-493F-80BD-F72C525D7F2E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"792cfb8f1604e9c7b9163c7b6a704699a9fe20ce","datavalue":{"value":"torus","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668022$41B7AE70-91E5-4900-9231-ED2A71C5F2A5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ed35a9fa19458304c0b74dd4e65451fe88c0a624","datavalue":{"value":"triangle-free","type":"string"},"datatype":"string"},"type":"statement","id":"Q2668022$AE809655-E154-43DF-8416-4A3AF34E7E31","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"b0b0cea8603b4de1ffd54cda6d37d129691a25c2","datavalue":{"value":{"entity-type":"item","numeric-id":590772,"id":"Q590772"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$675C9ABC-8AB2-4803-83F9-E77532F21993","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":"Q2668022$ED96D3DA-507A-48F5-AF9C-42CF8B8ED825","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"afb2edde281b704b246bcacb5fe6ef7815365dac","datavalue":{"value":"W3081822496","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$D099BF15-86B4-4FC4-9999-9FDF7D83710D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"28509d50213df601a56d81f32c56a205b49b545a","datavalue":{"value":{"entity-type":"item","numeric-id":2577175,"id":"Q2577175"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$1B13C801-A61C-41BF-888D-1AC223F6344D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3ab526e6cd047c661258c8b9f3d7302a4b09eb2d","datavalue":{"value":{"entity-type":"item","numeric-id":4065568,"id":"Q4065568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$F7A81194-9244-4CB2-9EAA-9BCAB8EAC4F5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"25bce8a5df0701ae39519ffc7c6271a89b95a22f","datavalue":{"value":{"entity-type":"item","numeric-id":2225450,"id":"Q2225450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$26F4C070-E5EC-4AF1-A2A2-37644D0800DB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"859ac532b345546c73ff0603e65dd474a52a4024","datavalue":{"value":{"entity-type":"item","numeric-id":723878,"id":"Q723878"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$8F349A5C-F3EF-418E-B37D-E663D9F5A72E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"54ba92fd26c7bdf80b70ec2dee03757c2e90e469","datavalue":{"value":{"entity-type":"item","numeric-id":2040021,"id":"Q2040021"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$3716C24F-0054-4EAF-8950-3FE0417531A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d4ae339d836265a996189c7df07879f3386b0577","datavalue":{"value":{"entity-type":"item","numeric-id":2664564,"id":"Q2664564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$EFB63306-75E7-4577-9A9C-34B5070EB62F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8878f4918b9611618979b470abbd8a49a94e429a","datavalue":{"value":{"entity-type":"item","numeric-id":4601215,"id":"Q4601215"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$CBEF77BE-E96F-4EA8-AB3C-9E81ECD02BD3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e31c4207af522bbd991cbbfd2180e7357a576da8","datavalue":{"value":{"entity-type":"item","numeric-id":4372592,"id":"Q4372592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$E69DA1BB-6382-4A72-915C-842981BB600F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c18ef0afbf5b62957150ab84b1ba3c519a86b140","datavalue":{"value":{"entity-type":"item","numeric-id":1880794,"id":"Q1880794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$F948A866-7543-4DD1-95C7-E818A048CCE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"187399749b9cbddae3c82e16af59c0db2746c526","datavalue":{"value":{"entity-type":"item","numeric-id":1338317,"id":"Q1338317"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$7BDA82B6-7961-46C6-8D15-B222B67D4B50","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d722e527436ab92c2de5bc5648be33aaffc90bf6","datavalue":{"value":{"entity-type":"item","numeric-id":1403910,"id":"Q1403910"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2668022$B044D314-4F31-4D20-8BD8-F0E6A0CE4BCF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d894c671684c035b413316b6d612ad4cd13761a2","datavalue":{"value":"10.1016/J.JCTB.2022.01.008","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2668022$CC06C665-87A0-4148-90AD-8CDD28897DD5","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"63aa12dbfac39706fe6ae61768ba015e2e120324","datavalue":{"value":{"entity-type":"item","numeric-id":3629461,"id":"Q3629461"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d3b7b461512837746bee3d4e1cd41d1e6f3f1854","datavalue":{"value":{"amount":"+0.8370751738548279","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":"Q2668022$963D3732-BD74-4E1A-AEC0-717F6A2A3E1A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3644dfe5a286211fdf20b3a4f92def2938fdf585","datavalue":{"value":{"entity-type":"item","numeric-id":4633818,"id":"Q4633818"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a361d6d0495231d1e96d4b036e6f7ec96eae1a30","datavalue":{"value":{"amount":"+0.8136005401611328","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":"Q2668022$A400E8F6-AE84-47AA-85E7-4DCCEF9B6DA0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5d560f93b65ea4a55a29ce7f79b486f0bc8ba766","datavalue":{"value":{"entity-type":"item","numeric-id":2664564,"id":"Q2664564"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"55a5663f7b96c00cbf3be10f608fce5150d9539c","datavalue":{"value":{"amount":"+0.8095661401748657","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":"Q2668022$19EE144D-D2E8-437A-99D8-ADC6D64C0AEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"992ea33a1f0d0d2ea2f5af3c2817d77938ff84a5","datavalue":{"value":{"entity-type":"item","numeric-id":949800,"id":"Q949800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2bbfe9e4a56368ab55371e8324e2abe5e2608c08","datavalue":{"value":{"amount":"+0.8073145151138306","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":"Q2668022$1D9C2823-3985-4CDD-BA93-DF774C302580","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"083778a005c49c8983af9e6ba295cb715c49a083","datavalue":{"value":{"entity-type":"item","numeric-id":2225450,"id":"Q2225450"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3f34d82d90cbc5ca2163c8bfa0aea13e204dc178","datavalue":{"value":{"amount":"+0.8066740036010742","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":"Q2668022$3C70BFE8-7A0C-4514-BAAF-89776BBD1557","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2668022","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2668022"}}}}}