{"entities":{"Q1849952":{"pageid":1860694,"ns":120,"title":"Item:Q1849952","lastrevid":74248221,"modified":"2026-04-14T19:10:36Z","type":"item","id":"Q1849952","labels":{"en":{"language":"en","value":"A note on the Gallai-Roy-Vitaver theorem"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1838938"}},"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":"Q1849952$41FED0AB-D864-4F4F-847C-0563A389FF6B","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"31877889132967f348962be328f1e82c187e16a6","datavalue":{"value":{"text":"A note on the Gallai-Roy-Vitaver theorem","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1849952$2871B21E-26BC-4ED3-87B0-B5A3CD0A5C27","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"47dbb25d55ac5091e937366bc060bd4dd12a50a2","datavalue":{"value":"1008.05055","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849952$64C265AA-85B9-459A-A13E-2870C014B30B","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"b3ca6b6cc3aeb0b462ea8c596f3ab1b4b8fb9eb0","datavalue":{"value":"10.1016/S0012-365X(02)00386-2","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849952$72F9D605-ED92-46A6-8647-2589FF266719","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"c8783284bba8a6466c7dcb01a7d6bcf4759911b8","datavalue":{"value":{"entity-type":"item","numeric-id":186291,"id":"Q186291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849952$A126E32B-CB88-4DB0-9C30-0EA4E33C49F8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"c4b757e83e2f91da3ed3ec3dfed7c13d9252967f","datavalue":{"value":{"entity-type":"item","numeric-id":186292,"id":"Q186292"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849952$AC03EDB3-8FAC-4B21-80C6-CAD63C0515DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"73c7847d8ff878c68f30cbc65ff523b663a8c4b5","datavalue":{"value":{"entity-type":"item","numeric-id":233434,"id":"Q233434"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849952$07F7D2B1-FD0D-418B-B1A7-078B17294B53","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"0b01296838df87730769f910acaeeb4756766580","datavalue":{"value":{"entity-type":"item","numeric-id":400523,"id":"Q400523"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849952$246AF69B-31BD-4702-85B3-8F84B5D1E582","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849952$EB3E716F-28CC-4A17-9946-178A718BA2AB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"82ac30fadc544187fd268bb88e1da4be75a5ee8c","datavalue":{"value":{"time":"+2002-12-02T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1849952$EC905EB7-240C-4D2E-8DD5-2A6A0F4BA290","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"98273d368501920d7a756ddca660dcfb57acf6ab","datavalue":{"value":"The main result of the paper states that for any proper colouring \\(f\\) of a connected graph \\(G\\) and for any \\(r\\) distinct colours \\(c_1,c_2,\\dots,c_r\\), there is a path \\(v_1,v_2,\\dots,v_r\\) in \\(G\\) such that \\(f(v_i)=c_i\\) for \\(1\\leq i\\leq r\\). It extends the well-known Gallai-Roy-Vitaver theorem [\\textit{T. Gallai}, Theory of Graphs, Proc. Colloq. Tihany, Hungary 1966, 115-118 (1968; Zbl 0159.54403), \\textit{B. Roy}, Rev. Fran\u00e7. Inform. Rech. Op\u00e9r. 1, 129-132 (1967; Zbl 0157.31302), \\textit{I. Vitaver}, Sov. Math., Dokl. 3, 1687-1688 (1963; Zbl 0126.39302); translation from Dokl. Akad. Nauk SSSR 147, 758-759 (1962)] and its extension proved by \\textit{H. Li }[Graphs Comb. 17, 681-685 (2001; Zbl 0989.05042)]. A shorter proof of Li's theorem and a counterexample to his conjecture concerning directed graphs is presented as well.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849952$1FAE3993-D9D8-4983-BF84-B37F31535C56","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849952$92935D05-49F3-4526-9A68-4A276C0DCA49","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849952$835BFD74-FB33-4287-8377-E82EB6C63AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"83bbf0b299346afb89579c3d6a26f4aedc76938a","datavalue":{"value":"05C20","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849952$B2B422B5-A48A-4EAD-85D9-5EC7EFEB3ED8","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"5f13eb734910ccaabe3dfdb426b14344f23302b4","datavalue":{"value":"1838938","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849952$A4E7D986-8AD2-40D6-862D-6728CC62985A","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"17b3416abeae8fe8e1dcfd57107eeffc6cfc00df","datavalue":{"value":"proper colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849952$5A0BD8A0-07D1-488B-BAC2-E228FB5D2149","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849952$7F3CB9AE-5BA2-45F5-A666-2FD1F66C65A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4aaaa8a20aebc13233df640115f8b0d384236cf5","datavalue":{"value":"path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849952$9D6CE188-10B3-4E26-90BC-5135AB3B4D83","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1db92bc7601eaee178ffaed0103e4107bc22c468","datavalue":{"value":"tournament","type":"string"},"datatype":"string"},"type":"statement","id":"Q1849952$0B7047E0-1FD9-4B8E-A673-3C102834CC41","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af45ac16b5c3b4cb5ad35340a1e807846a86d0e0","datavalue":{"value":{"entity-type":"item","numeric-id":593274,"id":"Q593274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1849952$351C9EDE-9F57-43CF-B665-6F876827B405","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":"Q1849952$1C8DA2F7-50BC-4EDC-8CCF-07E2C4502AF2","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"615087d322d76f2fc15e5ae0e8f600570e6372fc","datavalue":{"value":"https://doi.org/10.1016/s0012-365x(02)00386-2","type":"string"},"datatype":"url"},"type":"statement","id":"Q1849952$AB24C541-3901-4AC0-9DB8-59DBFA799ABB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"a95c99daa05480ae110f2054195c6b36ef5ea059","datavalue":{"value":"W2040811895","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1849952$332B599D-466E-454D-B05E-90BF04828FDA","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f2649a0f4acf93d49fe9d726acaae1dc6c5a221c","datavalue":{"value":{"entity-type":"item","numeric-id":5956104,"id":"Q5956104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"aa44f36cba73fd6ed3f92dc68990aba30ed8d4b8","datavalue":{"value":{"amount":"+0.8402383923530579","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":"Q1849952$29BF00AA-1ED1-4469-844A-7531279A0A1D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"b7634d0d35bde76922d8372149a23d3f6c754aef","datavalue":{"value":{"entity-type":"item","numeric-id":879947,"id":"Q879947"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"be09c6f7970cea114d526a6067b648f0b81e89b7","datavalue":{"value":{"amount":"+0.7910283803939819","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":"Q1849952$ED39DD43-FDA6-41E4-BB63-77CAE58C0745","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"44897ea9eaa52173896aa117d7ef389a0fb394c1","datavalue":{"value":{"entity-type":"item","numeric-id":540082,"id":"Q540082"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e66d56a8a6e6920323b595f05cf3a483c4d88cd7","datavalue":{"value":{"amount":"+0.7752273082733154","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":"Q1849952$14A345B7-36A0-40BC-B81B-29E0C20492DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"56c367bbd67a4b7c58de7c84d5e629d3f7becd8e","datavalue":{"value":{"entity-type":"item","numeric-id":943796,"id":"Q943796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"99a2b576fbb590e320aadbca6c95c15888116dd7","datavalue":{"value":{"amount":"+0.7719426155090332","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":"Q1849952$8327D0CD-B60C-4BBF-93CD-AC952A2331A1","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"A note on the Gallai-Roy-Vitaver theorem","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/A_note_on_the_Gallai-Roy-Vitaver_theorem"}}}}}