{"entities":{"Q1010637":{"pageid":1012485,"ns":120,"title":"Item:Q1010637","lastrevid":77732435,"modified":"2026-05-06T09:56:52Z","type":"item","id":"Q1010637","labels":{"en":{"language":"en","value":"Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5540855"}},"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":"Q1010637$3F26BCD1-50C7-4FBD-B29A-85336F4F9E04","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"994cd57fc43fc397f09eeb9f2f90554118c14f9d","datavalue":{"value":{"text":"Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1010637$EB1D6EF6-9518-46C8-87D7-3F678E413FF6","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"3820d2a0d48810d27254acd50de760c4fc497563","datavalue":{"value":"1182.05070","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010637$F8E708F8-9ECB-4292-B4A5-BAD3604F8F48","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"142cce64d0d1b2b55d8a1208b9a3c56a6dfbfc54","datavalue":{"value":{"entity-type":"item","numeric-id":251370,"id":"Q251370"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010637$C7E035A6-2334-443F-8BB4-2795225B26A4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2bf6b57361b3180efb360b271887d95e01377385","datavalue":{"value":{"entity-type":"item","numeric-id":831023,"id":"Q831023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1010637$04BA6FAD-E52E-4FB4-BDE2-1EA362696F40","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":"Q1010637$D39F428F-788B-4E1C-B902-878C28984DAB","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f584a175cfc2fafdfc362244f176e06010bbf381","datavalue":{"value":{"time":"+2009-04-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1010637$F408D53A-166C-4AF3-A121-CBE54B22F9D1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c9a2b1e1635f261275a9365a1ccc66236519a97b","datavalue":{"value":"https://arxiv.org/abs/math/0512144","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010637$DC84F337-16DC-4DD1-A00D-D2A104BF5AED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"52490a63c72dc4088ad51bebdcf4b9e15e475e7f","datavalue":{"value":"https://eudml.org/doc/117189","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010637$18FAE2D6-9D3E-46F3-8BEF-7CC8CE88DCFC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"7d0b7c58bd8143646f6f0f1f8e2ae252f176dbfb","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_14/Abstracts/v14i1r77.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q1010637$CAD5403D-18BD-4E50-B0DE-AC92DBE9485B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"ab1cf109f51267f60ca555eeb6c4d46d1628554c","datavalue":{"value":"Summary: Let \\(G\\) be an edge-colored graph. A heterochromatic (rainbow, or multicolored) path of \\(G\\) is such a path in which no two edges have the same color. Let \\(CN(v)\\) denote the color neighborhood of a vertex \\(v\\) of \\(G\\). In a previous paper, we showed that if \\(|CN(u)\\cup CN(v)|\\geq s\\) (color neighborhood union condition) for every pair of vertices \\(u\\) and \\(v\\) of \\(G\\), then \\(G\\) has a heterochromatic path of length at least \\(\\lfloor{2s+4\\over5}\\rfloor\\). In the present paper, we prove that \\(G\\) has a heterochromatic path of length at least \\(\\lceil{s+1\\over2}\\rceil\\), and give examples to show that the lower bound is best possible in some sense.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010637$1B93F0BD-4890-43A2-B3F5-AF2179DA0EF3","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010637$A7BFC476-396C-4D0E-9EBE-BF68D73DA814","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010637$075D4DBA-6BA4-473B-BB4D-A442C05587AF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"3cff63a482f3cfeee5a5a92d56d52f02f228bac1","datavalue":{"value":"5540855","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010637$9EC65DE2-BD41-4D34-AEA7-AD1EAADD6B35","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a35970f6c9d25db8fd6157359f5f87a41735c25d","datavalue":{"value":"edge coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010637$52E63D84-CF7B-495F-A146-387EBE2C34C1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"ffdbb27950124686648c9a805ed71bb0d1a0c734","datavalue":{"value":"heterochromatic path","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010637$5FB940E4-18B6-4F29-A8F2-A9700891C00D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a340e2ebc6ab9664146c8a91e8eaf432f75b6206","datavalue":{"value":"color neighborhood","type":"string"},"datatype":"string"},"type":"statement","id":"Q1010637$7A92E3FA-582D-4869-856D-8F857A3689E5","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":"Q1010637$684F808A-25CD-460B-B2F6-119865C35807","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"c6ec40dd0640474c7c5484ab518c93ec23362e0f","datavalue":{"value":"bafkreiaii5emivdec46awf4omy5aqmb3ouei4alz5uryi6suwwulkheo4u","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1010637$22021F8E-44C2-4FDB-8FBD-A6F1FD1AF771","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"81004c5440c5ed67ee91225f2ca4d10c3eb0e3ff","datavalue":{"value":{"entity-type":"item","numeric-id":2571276,"id":"Q2571276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"6a96a4f9e6b2accb4977c97446d6392ec9c61c13","datavalue":{"value":{"amount":"+0.9134446978569032","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":"Q1010637$23566BF8-774A-4DF3-B918-04A7E5A394FC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2625e6bed7677991ee46b8036119553841fe4941","datavalue":{"value":{"entity-type":"item","numeric-id":2948066,"id":"Q2948066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5fd415b4eb1f184b634a58a3aba107e23530a498","datavalue":{"value":{"amount":"+0.876123309135437","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":"Q1010637$65DCA757-FB3F-4A59-A3AD-907572EAAA02","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3294ca8083d22a954bcb0bdc011f9cf27e20d419","datavalue":{"value":{"entity-type":"item","numeric-id":5964923,"id":"Q5964923"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80f732bb50dee436d7f65fbf3220e5cff50e0f82","datavalue":{"value":{"amount":"+0.8699000477790833","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":"Q1010637$4004403C-2201-4586-B1F2-BC751D513F8E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3fc49e6a05266e2257139cfe2c4f57ff78d097eb","datavalue":{"value":{"entity-type":"item","numeric-id":2346583,"id":"Q2346583"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"cce81e72b3566db89cf6a58b12b1dc36878d990e","datavalue":{"value":{"amount":"+0.8455752730369568","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":"Q1010637$31AB9DA7-A153-4FB3-8948-D6AA73D859A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"319d5bcd09ac26a4c651eeb11bfde9b2a2fa26a1","datavalue":{"value":{"entity-type":"item","numeric-id":2816051,"id":"Q2816051"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49e9ae88dc782c27b315dc011784b8d900fad992","datavalue":{"value":{"amount":"+0.8401448726654053","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":"Q1010637$B0EA67DB-6544-4058-88E3-F1D44568D415","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Color neighborhood union conditions for long heterochromatic paths in edge-colored graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Color_neighborhood_union_conditions_for_long_heterochromatic_paths_in_edge-colored_graphs"}}}}}