{"entities":{"Q2656904":{"pageid":2667647,"ns":120,"title":"Item:Q2656904","lastrevid":56665701,"modified":"2026-03-18T13:44:00Z","type":"item","id":"Q2656904","labels":{"en":{"language":"en","value":"Determining the circular flow number of a cubic graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7323808"}},"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":"Q2656904$34F63578-89D0-44D0-A2F8-02A406063923","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fb8e9043e6db3336bbd5c9f45c096580b377cb77","datavalue":{"value":{"text":"Determining the circular flow number of a cubic graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2656904$5596E879-1B06-42FA-9494-7C93078F4B69","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"72101c9b25ea5996792f1a4832abf0800df319fe","datavalue":{"value":"1459.05109","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$831CDF3A-C49C-4DD4-9A10-43D70770F502","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"d9f067cd85c7213138f524d6ff58a41c26c14da8","datavalue":{"value":"10.37236/9607","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$5C76FBDF-4396-4DED-A83F-DBCBFD70FC1B","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"aaf718c5b28e0f5126a78ca32045d5bdb8e5e3ad","datavalue":{"value":{"entity-type":"item","numeric-id":490311,"id":"Q490311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$C6DD4129-5848-46D0-9258-C7B6F8EE398C","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":"Q2656904$A7D8F695-64C0-4331-A9F4-1B4570570522","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c44e9e40e16b91f474187fb226cbd1d827ea50c7","datavalue":{"value":{"time":"+2021-03-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2656904$2DB9829A-6960-41B4-A0A2-B67F30D497F7","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"baf8951d5d0b8233465d3491720a491832318292","datavalue":{"value":"Summary: A circular nowhere-zero \\(r\\)-flow on a bridgeless graph \\(G\\) is an orientation of the edges and an assignment of real values from \\([1, r-1]\\) to the edges in such a way that the sum of incoming values equals the sum of outgoing values for every vertex. The circular flow number, \\(\\phi_c(G)\\), of \\(G\\) is the infimum over all values \\(r\\) such that \\(G\\) admits a nowhere-zero \\(r\\)-flow. A flow has its underlying orientation. If we subtract the number of incoming and the number of outgoing edges for each vertex, we get a mapping \\(V(G) \\to \\mathbb{Z} \\), which is its underlying balanced valuation. In this paper we describe efficient and practical polynomial algorithms to turn balanced valuations and orientations into circular nowhere zero \\(r\\)-flows they underlie with minimal \\(r\\). Using this algorithm one can determine the circular flow number of a graph by enumerating balanced valuations. For cubic graphs we present an algorithm that determines \\(\\phi_c(G)\\) in case that \\(\\phi_c(G) \\leqslant 5\\) in time \\(O(2^{0.6\\cdot|V(G)|})\\). If \\(\\phi_c(G) > 5\\), then the algorithm determines that \\(\\phi_c(G) > 5\\) and thus the graph is a counterexample to Tutte's 5-flow conjecture. The key part is a procedure that generates all (not necessarily proper) 2-vertex-colourings without a monochromatic path on three vertices in \\(O(2^{0.6\\cdot|V(G)|})\\) time. We also prove that there is at most \\(2^{0.6\\cdot|V(G)|}\\) of them.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2656904$F83DBBDA-DF54-42C2-AF97-FEF10F61BDF9","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6ffc362644ca7876fb8337c4e7378fca3f3c2090","datavalue":{"value":"05C21","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$E4C522DD-70E0-40C2-B1C3-2EB9FA899B18","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"1de0493fc6f7fe4361a54e7c2f5546e4ec52adf0","datavalue":{"value":"05C30","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$898542F4-2E85-483A-B227-20569821B4AF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"749b7137f279a66a306e75e15f613231b281c1c5","datavalue":{"value":"05C85","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$0AC22A8F-B260-4E9C-8031-717C797ABF22","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"20c3801b7129bb8eceb6682eefafa8ed791ff93e","datavalue":{"value":"7323808","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$648B0ED6-6E75-4765-870F-1348764AAB81","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"23489001fcde6a15e45c98c51d0ba11fc009c393","datavalue":{"value":"bridgeless graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2656904$1F32D454-0405-4E0E-9557-FEA5B6D6E8E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"3b6d19d4c43b54c850c0e7b873f523866d352b6c","datavalue":{"value":"polynomial algorithms","type":"string"},"datatype":"string"},"type":"statement","id":"Q2656904$E6D49AEA-F9A9-45DA-BD31-D548B49CE3DC","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":"Q2656904$B11FCEB8-93A3-4A46-8181-14FBCFE43B35","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"d9ad1cb7e8fcfe0ee5998519af85ab4ce9f5a869","datavalue":{"value":"https://doi.org/10.37236/9607","type":"string"},"datatype":"url"},"type":"statement","id":"Q2656904$36289EE6-55A5-4D94-96CC-242AEEE79AF8","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"e625b1054e120e093e32c4766eeab7a6f07a30bd","datavalue":{"value":"W3136748713","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$E39AD5FD-5BDF-418F-B618-F1DC3B3471B6","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"249545f0311e51fdc7f6a5fd69d837cb8642734f","datavalue":{"value":{"entity-type":"item","numeric-id":1112026,"id":"Q1112026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$FC209975-C690-467F-B9E0-A33693FCB04C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5898a3a95e1b0606e52aa24c79d5a6dc96dd2a74","datavalue":{"value":{"entity-type":"item","numeric-id":1045933,"id":"Q1045933"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$313D924C-752A-4602-9DD3-30B6589CA65D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"95df34df3ebff8e43b98456d850716267bbafc6a","datavalue":{"value":{"entity-type":"item","numeric-id":4242967,"id":"Q4242967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$30A465D9-3C1E-4DAF-9A99-E7ABCC1DA1FB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d55c691469a5eaf6da52a5c84a43678168cbd2f0","datavalue":{"value":{"entity-type":"item","numeric-id":785826,"id":"Q785826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$12A2C2AA-196D-4E58-BE95-59053523F633","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c89e671bd1c33e22efaade536bbabc8a1d349606","datavalue":{"value":{"entity-type":"item","numeric-id":3158520,"id":"Q3158520"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$9B487AEC-8C41-480D-BCCF-D7EF987E626E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0c439d80aa48b2235589f2742abd16fc8d19d0fd","datavalue":{"value":{"entity-type":"item","numeric-id":2532282,"id":"Q2532282"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$6BF17F8C-6DA5-4455-A63B-A58DC69B12EB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"284cb909caaf4edaadd582505d5808286fe39d1f","datavalue":{"value":{"entity-type":"item","numeric-id":1748263,"id":"Q1748263"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$7E30630A-D96C-4E81-BCC2-A6AE0D12569D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"631200adace0f14c2f6d92fc47cb2d9f5d82cdbb","datavalue":{"value":{"entity-type":"item","numeric-id":3928241,"id":"Q3928241"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$9F1575D5-B18F-435B-BE3D-E8DF8C27ABB3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38429ee94b1151930f2c2317784ebfbcbf68b58d","datavalue":{"value":{"entity-type":"item","numeric-id":4085742,"id":"Q4085742"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$9934AC74-61CB-43B2-A616-2CA9BFAB1492","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"647c6598550787528a69aa8b1446a97da6d42371","datavalue":{"value":{"entity-type":"item","numeric-id":3682525,"id":"Q3682525"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$F34B66EA-459B-4CE4-BD75-959A27F67001","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b2eca27bb5ac35d87ebc19a3603dc6192d1705ae","datavalue":{"value":{"entity-type":"item","numeric-id":3528156,"id":"Q3528156"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$42E32A6D-D935-410A-9BF2-695C3AF7A42F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c4c507e31c9f19be29ef0c21a42fe9d0aa0833da","datavalue":{"value":{"entity-type":"item","numeric-id":1159209,"id":"Q1159209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$371C573C-B909-43A7-AFA3-AD4D0C2C6CB9","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c76a7aec0ced5818330ce1dee27ebe582c2dfe39","datavalue":{"value":"bafkreihpk73blly7tuzpasnb7ol2ns3jjvt5n3d5dgtmbifsvr2wvr6vk4","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2656904$D13D4A9B-3C74-4A7D-84C9-096964835E83","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3161dbdc6e3fb63508ae0e22570e405f59ce6821","datavalue":{"value":{"entity-type":"item","numeric-id":2142658,"id":"Q2142658"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5b5dfa28ea04605392bc7e29ed7c4317593a71c8","datavalue":{"value":{"amount":"+0.8262516260147095","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":"Q2656904$1A4C0E49-7495-4FB2-99FB-69FDE47EF42B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c503701faee75abe3be5429f3d71cc8fff39e00b","datavalue":{"value":{"entity-type":"item","numeric-id":785826,"id":"Q785826"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"642f482a52681cf9a028385b8ffa4bb3b24d5d76","datavalue":{"value":{"amount":"+0.8139264583587646","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":"Q2656904$9DA85D47-C75B-4190-9921-0C5433F44F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6db21e61b8e4698559ef5ba70aa125a9b019d1a8","datavalue":{"value":{"entity-type":"item","numeric-id":5272921,"id":"Q5272921"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c8bbb09c16e4e28bfac4bbbf8243dcb8f01b8354","datavalue":{"value":{"amount":"+0.8058939576148987","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":"Q2656904$05CCB55D-ECB5-48B8-833B-F14407EAFD9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9612418adae625993c8c237bf31dc09e8dec4ee9","datavalue":{"value":{"entity-type":"item","numeric-id":2708793,"id":"Q2708793"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4924133aab78b0b3560bc0f3286c44f868334516","datavalue":{"value":{"amount":"+0.8056932687759399","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":"Q2656904$E93AEC07-18B6-459F-A48B-A9727F7DE27A","rank":"normal"}],"P163":[{"mainsnak":{"snaktype":"value","property":"P163","hash":"45fcd4163b5f33e6e8c784f5522d7246c0a1a61e","datavalue":{"value":{"entity-type":"item","numeric-id":57056,"id":"Q57056"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2656904$AD7E3A96-E78B-4EEB-8008-0E7BE19CB556","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2656904","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2656904"}}}}}