{"entities":{"Q2713622":{"pageid":2724361,"ns":120,"title":"Item:Q2713622","lastrevid":55856188,"modified":"2026-02-20T13:40:08Z","type":"item","id":"Q2713622","labels":{"en":{"language":"en","value":"A note on the road-coloring conjecture"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1602755"}},"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":"Q2713622$6CF72C8E-F7C3-414C-96ED-FCFB8595D11A","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"9b05b9d5563f0037abebd2204269c2381267893c","datavalue":{"value":"0963.05059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713622$D167829A-74C2-42D7-BD6E-2DA59AC4B25F","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6d02c02a8694a5ae48849b5ac30a19429f65d0e7","datavalue":{"value":{"entity-type":"item","numeric-id":2713621,"id":"Q2713621"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713622$CEB3BAE8-C1BC-4C43-900C-E71D4AFF33F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a0ec2208b25ece90cbfecb2a3cc411806b924f37","datavalue":{"value":{"entity-type":"item","numeric-id":1111378,"id":"Q1111378"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713622$53949669-3B4B-4FC3-BC77-CE16FFE72024","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"41fca74e9950a16c663ca86f884e7b8febbc1dc4","datavalue":{"value":{"entity-type":"item","numeric-id":290246,"id":"Q290246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713622$01BA4184-30E7-48BB-A7F6-83F17D38E5FF","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"d399175a75045d6e68cdfc363866ce63dcafb225","datavalue":{"value":{"time":"+2001-06-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":"Q2713622$AD31C2C2-940F-41E7-9DB4-216B9C3EA0C8","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713622$B4482451-17DE-4054-90B8-5D8A4A7DE590","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b78776a56fc28cdd893baa47605a105412b838a","datavalue":{"value":"68Q45","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713622$8FAE5BD4-C881-4E3F-8F9B-83604FAA5AC8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"71da8be60bf0e77d4d8d5b861fc7df34ca01d66b","datavalue":{"value":"1602755","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2713622$83D1F937-66AD-4CA7-8B84-B4048D1818C3","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2628872f454b5aa47f0823edc08a495e20179843","datavalue":{"value":"road-coloring conjecture","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713622$12B10475-D56C-4754-823C-9E256626D5D2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"f4b98b5353082f5ae3dd3eedbb2c57d8903e4ca5","datavalue":{"value":"directed graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713622$66CA7C97-B58C-4781-A23E-8D827301DC0F","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":"Q2713622$DF8D9E3F-C48E-4B29-9F53-29A1F0DFF975","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"ca56dd86b6a07d74639f49feaa56da1b5153e289","datavalue":{"value":{"text":"A note on the road-coloring conjecture","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2713622$F96E4118-0B3F-4B44-B1C5-F64D4DDBCA2B","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"6f7fbf6651880b9d76c5e78437f7f8284b8f74c4","datavalue":{"value":{"entity-type":"item","numeric-id":6550664,"id":"Q6550664"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2713622$AB74F97E-E543-41DB-B6B3-1CE6854D7BEC","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ac6fd57218fca67b189bb9dc087b8b911d0001a2","datavalue":{"value":"This paper contains some results related to the road-coloring conjecture of Alder, Goodwyn, and Weiss. Using probabilistic methods, it is shown that if \\(\\delta =\\Omega (\\log n)\\), then the road-coloring conjecture is true for almost every strongly connected aperiodic directed graph on \\(n\\) vertices of outdegree \\(\\delta \\). An \\(O(n^2)\\) algorithm for determining whether or not a particular road-coloring is a resolving one is also given.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2713622$2B0843EA-4A77-4174-B9E1-BFE2C9A2E2B2","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"153a4050bb209cba3e0a7c3826a0aba6991d7814","datavalue":{"value":{"entity-type":"item","numeric-id":3576704,"id":"Q3576704"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"0a268850883308accae296ef926ecc373350b680","datavalue":{"value":{"amount":"+0.8701371550559998","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":"Q2713622$7FF6ED34-D466-4222-BAD9-9B1764642D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2b201bdccf11726387023e274749c98bfaeacca3","datavalue":{"value":{"entity-type":"item","numeric-id":3970256,"id":"Q3970256"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6876c6c25fae7d155ce263b2c786b39ce7656ad6","datavalue":{"value":{"amount":"+0.8500836491584778","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":"Q2713622$FB62518D-F906-4A9A-A8AB-2B774388BA80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"84cf81622977614126bb80f892b2aa4285f26d87","datavalue":{"value":{"entity-type":"item","numeric-id":5939288,"id":"Q5939288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80ed99ae4adcad345ff2697626a3bebd71085e59","datavalue":{"value":{"amount":"+0.8486943244934082","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":"Q2713622$643DB9E6-0B51-42E5-9624-9C3AB76C9A72","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":"8f1d49e316d50c6c36196c9581684dc84a87939f","datavalue":{"value":{"amount":"+0.8377299904823303","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":"Q2713622$F58B3BBB-3388-4FE1-AFBE-4A0AF68FF7E2","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2713622","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2713622"}}}}}