{"entities":{"Q405138":{"pageid":406905,"ns":120,"title":"Item:Q405138","lastrevid":61599780,"modified":"2026-04-11T00:23:21Z","type":"item","id":"Q405138","labels":{"en":{"language":"en","value":"Rainbow path and color degree in edge colored graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6340144"}},"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":"Q405138$21A63BA9-1877-41E8-AEF6-2E359346D560","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"9e016f12292c7b6743f45f220973548eeb8f2946","datavalue":{"value":{"text":"Rainbow path and color degree in edge colored graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q405138$908ADDD3-D9DD-4A77-945A-6536678799E7","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"eab81168f49da45d064eeada668b85bdc6d5885f","datavalue":{"value":"1300.05094","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405138$1B718E49-B9ED-4E9F-ACF1-75FA41B1E1CC","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":"Q405138$1B40CF14-5B14-497C-A014-FD71CBA87423","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"f9d8fea32a46af1bd8128cc5dcfc32073a3817d0","datavalue":{"value":{"time":"+2014-09-04T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q405138$33BFA42D-965F-4367-A06F-BAA07048C803","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"92b8b9582949b9b7879c23745801e8ede24f8821","datavalue":{"value":"https://arxiv.org/abs/1312.5067","type":"string"},"datatype":"url"},"type":"statement","id":"Q405138$969DD57A-C4D2-4B71-8D45-FDA99E3D5A15","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"271e2393e1bdeea72b16c0cdfd763335a60db8ea","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p46","type":"string"},"datatype":"url"},"type":"statement","id":"Q405138$173FB168-E896-4414-906F-6102CDE2F894","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5a9ac9aae91649cd26f2b1375253359adceedd29","datavalue":{"value":"Summary: Let \\(G\\) be an edge colored graph. A rainbow path in \\(G\\) is a path in which all the edges are colored with distinct colors. Let \\(d^c(v)\\) be the color degree of a vertex \\(v\\) in \\(G\\), i.e. the number of distinct colors present on the edges incident on the vertex \\(v\\). Let \\(t\\) be the maximum length of a rainbow path in \\(G\\). \\textit{H. Chen} and \\textit{X. Li} [ibid. 12, No. 1, Research paper 33, 32 p. (2005; Zbl 1080.05047)] showed that if \\(d^c \\geq k \\,\\, (k\\geq 8)\\), for every vertex \\(v\\) of \\(G\\), then \\(t \\geq \\left \\lceil \\frac{3 k}{5}\\right \\rceil + 1\\). Unfortunately, the proof by Chen and Li is very long and comes to about 23 pages in the journal version. Chen and Li states in their paper that it was conjectured by Akira Saito, that \\(t \\geq \\left \\lceil \\frac {2k} {3} \\right \\rceil\\). They also state in their paper that they believe \\(t \\geq k - c\\) for some constant \\(c\\). {  }In this note, we give a short proof to show that \\(t \\geq \\left \\lceil \\frac{3 k}{5}\\right \\rceil\\), using an entirely different method. Our proof is only about 2 pages long. The draw-back is that our bound is less by 1, than the bound given by Chen and Li. We hope that the new approach adopted in this paper would eventually lead to the settlement of the conjectures by Saito and/or Chen and Li.","type":"string"},"datatype":"string"},"type":"statement","id":"Q405138$23748450-4B35-4B0F-A855-BB67C3C0F0BE","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405138$BB87AE6B-F96F-4971-9146-EB7AC2700F82","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405138$C13B9318-1194-4684-9E3A-4AB127456674","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"0eb641dfbfdde552c13c3490b1b096e8de308421","datavalue":{"value":"6340144","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405138$37F32FD7-B78C-4DE4-9755-98B6CEB28AF6","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"21b811b2f8236f4959646be0adaf22fe9623da59","datavalue":{"value":"edge colored graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q405138$CBFB8D1A-F04D-40A2-8F7A-E6B727D72057","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7740089849c4786bbd095fc898acf26d17e3722","datavalue":{"value":"rainbow path","type":"string"},"datatype":"string"},"type":"statement","id":"Q405138$74EFB1D9-3261-4A53-BD68-588C2BCC4302","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9c8014566145ab7a1c919203a63eb16e3210a178","datavalue":{"value":"color degree","type":"string"},"datatype":"string"},"type":"statement","id":"Q405138$B36FD6DC-0903-43D3-92B3-4DECB28EEA86","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":"Q405138$3F1482F4-F291-46AF-A684-EAF3F6FEF07D","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bf2b7dd29f8cf638bc89994c0157240c328ee31e","datavalue":{"value":{"entity-type":"item","numeric-id":5294911,"id":"Q5294911"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405138$2C33B392-25F4-4EA5-AC45-0340BBD8AF9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"849c55314eb788259d257782339f298d231a4af5","datavalue":{"value":{"entity-type":"item","numeric-id":2571276,"id":"Q2571276"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405138$C4AFCD9D-BE9B-474E-A1C2-CA5533789EA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c51331430409870f4fe1456725db1af6343410ad","datavalue":{"value":{"entity-type":"item","numeric-id":3576975,"id":"Q3576975"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405138$8C21A78D-2A89-44F5-AD88-0E4338792CD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"df0d84e7844e0c25159ad49111bfe8e9e012ddfd","datavalue":{"value":{"entity-type":"item","numeric-id":1014813,"id":"Q1014813"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405138$669E8510-8A15-4448-8746-5ACE345C3CC7","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"4dc984a2d6753e27fd63c6fcd62ee37f82fce590","datavalue":{"value":"bafkreigojbtngxyvxqbu3ppp4xsy7ec5hjez3qjikfao3lm7pigubmyxsm","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q405138$62E83FEA-8024-4FC5-BF9C-B61EA070BC68","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"4155dc2e61a65766a994ad6eab510038f996522e","datavalue":{"value":{"entity-type":"item","numeric-id":608274,"id":"Q608274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405138$78920023-41AA-49AD-A0C3-A96073E87793","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5464b47a0d74622a8bdf17b15b5d6e51603e5ae0","datavalue":{"value":{"entity-type":"item","numeric-id":385877,"id":"Q385877"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405138$667EAC6C-6F61-4CBB-B514-0E971A9928F3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"dad60645292f47ddc10e1ae35ff230ec20a4bb63","datavalue":{"value":{"entity-type":"item","numeric-id":6773796,"id":"Q6773796"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q405138$CA63E7F0-A0E3-454E-BD8D-47782E2CA906","rank":"normal"}],"P1643":[{"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":"0d5e0449fdc57feaf5ea1fe21d8471fcce90a9ac","datavalue":{"value":{"amount":"+0.9078513979911804","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":"Q405138$EE4EB76F-A6E5-4575-B81C-168AF4BA56BC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e413259f458c4e985f5be40aceddefb40624c7ab","datavalue":{"value":{"entity-type":"item","numeric-id":3382209,"id":"Q3382209"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"5747b4480cfcfbc2a600b566099b74e5b1fce19f","datavalue":{"value":{"amount":"+0.8938931226730347","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":"Q405138$61A43DD3-5C91-4DF1-A237-1336CC6A8368","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"70140bdc9fd9c453c1c9141a22658dcf5443353f","datavalue":{"value":{"entity-type":"item","numeric-id":5419984,"id":"Q5419984"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8739dabacf8fbf44e54c95fd12808b0a0b51bb39","datavalue":{"value":{"amount":"+0.8683629631996155","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":"Q405138$14BE3C67-24D4-42E4-902D-048648F28B11","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f4e5832675e986c6ee4480d6e3553c3b424c5051","datavalue":{"value":{"entity-type":"item","numeric-id":965956,"id":"Q965956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4b5f4eca300a95330334c8a633695fbfa0467117","datavalue":{"value":{"amount":"+0.8336517214775085","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":"Q405138$26D6D7C6-A9E8-42E9-941D-7FF0A1E4580A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"578040863fc849b878b178c84b38560bef0e88bb","datavalue":{"value":{"entity-type":"item","numeric-id":2441651,"id":"Q2441651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"80f3a2f620ae82bb1efe9e05dd1fea38e02d35e5","datavalue":{"value":{"amount":"+0.8316916823387146","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":"Q405138$8DC9290F-5BB0-4318-B216-C0B9F6188DE5","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rainbow path and color degree in edge colored graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Rainbow_path_and_color_degree_in_edge_colored_graphs"}}}}}