{"entities":{"Q5939288":{"pageid":8116090,"ns":120,"title":"Item:Q5939288","lastrevid":47648452,"modified":"2026-01-02T07:38:01Z","type":"item","id":"Q5939288","labels":{"en":{"language":"en","value":"Cycles of relatively prime length and the road coloring problem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1625485"}},"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":"Q5939288$93895B95-333F-40E1-95B2-999F2C488D68","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"7befdecacf3d6473c4007bdfa16058f2ff1be289","datavalue":{"value":{"text":"Cycles of relatively prime length and the road coloring problem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q5939288$D54641CC-920B-469D-8720-B6026E71B295","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7e3e8074f5cbca2d18c5f67260738e15ab9e7e53","datavalue":{"value":"0979.05046","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939288$2BF863B0-CF98-4910-A50C-5B05CF516080","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"2491565c1aba30eaf497f8c6a9fb673d7efd23fb","datavalue":{"value":"10.1007/BF02784133","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939288$1E6BE403-5885-48F3-9E44-E4D542095B5F","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"1d50f9b953eac0b2404563f86ad398ee3823cb48","datavalue":{"value":{"entity-type":"item","numeric-id":173732,"id":"Q173732"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$385CFFA7-EAD9-4EB7-B14B-DBB9C68AB38E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"63e1d7063ecd638677848b844accef77290c7ea4","datavalue":{"value":{"time":"+2002-02-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":"Q5939288$A50BE2DB-F6E3-4F54-92B6-CC515F94C124","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"7e83067efaccff8f4bddf784cbb48e46665e531f","datavalue":{"value":"A directed graph \\(G=(V,E)\\) is given in such a way that each outdegree is \\(k\\). We label each edge of \\(G\\) with one of \\(k\\) labels in such a way that for each vertex \\(v\\) and each label \\(l\\) there is a unique edge \\(e\\) leaving \\(v\\) and having label \\(l\\). Such a labeling is said to be a synchronizing coloring of \\(G\\) if there is a certain sequence \\((l_1,l_2,\\ldots,l_m)\\) of labels, so that for any vertex \\(v\\) of \\(G\\) the walk that starts from \\(v\\) and follows the edges labeled with \\(l_1,l_2,\\ldots,l_m\\) always ends at the very same vertex \\(w\\) of \\(G\\), independently of \\(v\\). The road coloring problem is to find a synchronizing coloring for a given graph \\(G\\) as above. Clearly, a synchronizing coloring cannot exist if \\(G\\) is periodic, that is \\(V\\) can be partitioned into parts \\(V_1,V_2,\\ldots,V_p\\) so that each edge goes from some \\(V_i\\) to the next part \\(V_{i+1}\\) (addition is modulo \\(p\\)). It is generally believed that for any aperiodic graph (a graph that is not periodic, or in other words, a graph that contains some directed cycles that have relatively prime length) there always exists some synchronizing coloring. The paper justifies this belief for certain classes of graphs. The basic idea is to find label-sequences for a given labeling that ensure that the corresponding path ends on a certain cycle. As a corollary a related earlier result of \\textit{N. Jonoska} and \\textit{S. Suen} [Monocyclic decomposition of graphs and the road coloring problem, Congr. Numerantium 110, 201-209 (1995; Zbl 0905.05066)] is deduced. The proof of the most general condition involves some number theory, namely the Chinese remainder theorem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939288$5B0EEB9E-DC7F-4B3D-AD04-A56144FDC7EB","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"d4de3193b89da1a841d76ad5faa949e9be96ad30","datavalue":{"value":{"entity-type":"item","numeric-id":228803,"id":"Q228803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$630EE2BD-3D80-4902-B6D2-4E2DA33153BD","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939288$10881B61-8B5D-4E40-BAB4-AB6708502524","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939288$BD682D37-1227-442E-BAE6-385606F257CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939288$CA3799BC-35D0-40C6-80A9-B13D4C1F16B8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91639960447c8da747fe8650ceb25868573f3f13","datavalue":{"value":"1625485","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939288$3173A04D-E139-439F-BB2F-6C61294EFAC8","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1ae6cc52b35d03b83d5162d854c61cf5b039329e","datavalue":{"value":"cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939288$4F7AB456-04C4-48B7-82BB-45F8B97CDA7D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939288$330CCE03-E946-4217-9656-74A370E20E2A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"010a5a2741bd773cdb0d39cd574a5581e8be2992","datavalue":{"value":"road coloring problem","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939288$80E45E2F-97BD-400E-BE2A-43399780CE33","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"479c39503aea7153690b6f692446b94b4edcc871","datavalue":{"value":"synchronizing coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q5939288$7AFDD091-2639-4768-8661-99958B068C35","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":"Q5939288$59DD2FBF-C346-40E0-8241-999DE63E596E","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"79c324461fe0947ad22563dedf01b00c2f872caa","datavalue":{"value":{"entity-type":"item","numeric-id":1239939,"id":"Q1239939"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$DBEE0969-1CFF-4B7F-A6A2-DE84739773A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"82b49fbf5b4677549882aa78318db9f0348c2844","datavalue":{"value":{"entity-type":"item","numeric-id":5590876,"id":"Q5590876"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$F15E64B3-8BAC-4F11-BAAE-949D4D64ED41","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2e235b495c0979d0b0c72356d94803551cdd7a97","datavalue":{"value":{"entity-type":"item","numeric-id":3970256,"id":"Q3970256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$614CD4D1-829B-47E4-A9BA-A70423F58A80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d580cacf7e5301af2e55fcd0d0fed2b6970eac73","datavalue":{"value":{"entity-type":"item","numeric-id":3838420,"id":"Q3838420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$08D90BB3-C3FC-4999-B64E-C0B491B04856","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"137fdba97c012d893979a5ff2c393f716ec51578","datavalue":{"value":{"entity-type":"item","numeric-id":1157339,"id":"Q1157339"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$79E8EFED-666D-4F36-AFFC-28F5032FD29A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d32bf7d53fda838042e7a1e071f2f5fe8be46dce","datavalue":{"value":{"entity-type":"item","numeric-id":4173294,"id":"Q4173294"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$0BBF753E-F3FE-4DE6-8DE6-C2C070D4B3DF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d1fa39e5d9706f4563608745a0f01391754ab786","datavalue":{"value":{"entity-type":"item","numeric-id":4037012,"id":"Q4037012"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$117B22AD-C09F-4AC7-917C-A349447029ED","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"2483ac2c415e718411c7dba9607b266acfa1de81","datavalue":{"value":"https://doi.org/10.1007/bf02784133","type":"string"},"datatype":"url"},"type":"statement","id":"Q5939288$D124A59A-D7EB-4A52-822A-D7F804BEA7D4","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2e940fd02068a0ac88efb2ce2b05d502c0112007","datavalue":{"value":"W2067312148","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q5939288$219A3AF6-2F62-4FEE-B630-C6608FDA74CB","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"90003f443fd2ea1d4e4b90665282b4ffee87ad13","datavalue":{"value":{"entity-type":"item","numeric-id":2004675,"id":"Q2004675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q5939288$543DA836-576B-49C5-A78B-07A740958285","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a1ec5c27b34fff37dbf93c620b263e62cce1047c","datavalue":{"value":{"entity-type":"item","numeric-id":3838420,"id":"Q3838420"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4937c0db184d02a33e54348a7af5e7bae577fd34","datavalue":{"value":{"amount":"+0.8900375962257385","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":"Q5939288$8FE742E9-FBF6-47CC-91A4-1BCB2D849333","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"660e7a9bdce60ba559dcf5b3da4c8fa62cb80084","datavalue":{"value":{"entity-type":"item","numeric-id":731355,"id":"Q731355"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8faddc0583ab775b5cf25c48bd9efc26b27fe070","datavalue":{"value":{"amount":"+0.8689485788345337","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":"Q5939288$A59ED794-D852-4849-B2AF-79D206210D5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"40881576b56f56ace6df5bdc67913e02d20c2dbf","datavalue":{"value":{"entity-type":"item","numeric-id":3569761,"id":"Q3569761"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"43734a9407ebbf30c8e240165e96d136a99b541e","datavalue":{"value":{"amount":"+0.8602678775787354","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":"Q5939288$E19E3588-0B77-43B9-B390-B2D229404CD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6a8a04bd0f5f92f285bdfc68a9119a45f81b044","datavalue":{"value":{"entity-type":"item","numeric-id":2449052,"id":"Q2449052"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"967978e829a68b6f701eb106366e9f92a6cc5f36","datavalue":{"value":{"amount":"+0.8578540086746216","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":"Q5939288$9F81005F-8318-4D40-B039-1DBD493F8A4F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41af656e9f9e7da2a09248356c31a7fd0ca7ea35","datavalue":{"value":{"entity-type":"item","numeric-id":4737905,"id":"Q4737905"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ef50643c2c358fd71f299f276ed12406766c99f8","datavalue":{"value":{"amount":"+0.8494498133659363","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":"Q5939288$905E94CD-EBD5-4A41-8C0A-F047D9C3BA83","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:5939288","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:5939288"}}}}}