{"entities":{"Q540082":{"pageid":541849,"ns":120,"title":"Item:Q540082","lastrevid":62605371,"modified":"2026-04-11T07:13:30Z","type":"item","id":"Q540082","labels":{"en":{"language":"en","value":"Rainbow paths with prescribed ends"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5903016"}},"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":"Q540082$650F78AD-B34E-4327-B2D1-0A9369BAA9D7","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"97bd1d2574698ea2e1084b481719d99f467ee93b","datavalue":{"value":{"text":"Rainbow paths with prescribed ends","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q540082$BB2293AD-5205-4FF2-A7FC-D3320378C844","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"008974f05f94f742975f13af1f158fe7797d3d7c","datavalue":{"value":"1218.05044","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540082$89627A51-FCDE-4A95-9534-0E2E13DDF1DE","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2a146e7e7774eafed2ceb420a5c8180f7578555c","datavalue":{"value":{"entity-type":"item","numeric-id":490991,"id":"Q490991"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540082$C487EFEC-CBC5-4087-9D25-3F69B19D0358","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bc7396155e0529c760f980b1b36a7b8b6550cbd8","datavalue":{"value":{"entity-type":"item","numeric-id":540081,"id":"Q540081"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540082$B65E821A-8422-4A50-96C9-0EFEFCAC640F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"aec857263cee52fe850f36c12f5157e5c8f0a013","datavalue":{"value":{"entity-type":"item","numeric-id":228790,"id":"Q228790"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q540082$5A796C9C-7690-4593-B314-7DAF9E647319","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":"Q540082$6F9F9519-0168-42EB-9FDB-F338E81D7D68","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"ca412915d48bc02df19cbc26b81271d64e23ee32","datavalue":{"value":{"time":"+2011-06-01T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q540082$6D2B7B1E-6AD0-4A5D-AE8C-FC05840272C8","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"f18d7d5baa6edb5690fae7a9f3161b599d761fe1","datavalue":{"value":"https://eudml.org/doc/231758","type":"string"},"datatype":"url"},"type":"statement","id":"Q540082$85DC7656-D702-4188-97F3-6CDCCC92A8CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"a44b324e18e3d9f1e1a77459a232939d620ed8fa","datavalue":{"value":"http://www.emis.de/journals/EJC/Volume_18/Abstracts/v18i1p86.html","type":"string"},"datatype":"url"},"type":"statement","id":"Q540082$A67B93E1-7D62-4158-A1C3-26AE54A82385","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"8ed6bc9588b619613a8a2321faeb3ed9fdd8b2ca","datavalue":{"value":"Summary: It was conjectured in [\\textit{S. Akbari}, \\textit{F. Khaghanpoor}, and \\textit{S. Moazzeni}, ``Colorful paths in vertex coloring of graphs,'' Preprint] that, if \\(G\\) is a connected graph distinct from \\(C_7\\), then there is a \\(\\chi(G)\\)-coloring of \\(G\\) in which every vertex \\(v \\in V(G)\\) is an initial vertex of a path \\(P\\) with \\(\\chi(G)\\) vertices whose colors are different. In [\\textit{S. Akbari}, \\textit{V. Liaghat}, and \\textit{A. Nikzad}. ``Colorful paths in vertex coloring of graphs,'' Electron. J. Comb. 18, No.\\,1, Research Paper P17, 9 p., electronic only (2011; Zbl 1290.05070)] this was proved with \\(\\left\\lfloor \\frac{\\chi (G)}{2} \\right\\rfloor \\) vertices instead of \\(\\chi (G)\\) vertices. We strengthen this to \\(\\chi (G) - 1\\) vertices. We also prove that every connected graph with at least one edge has a proper \\(k\\)-coloring (for some \\(k\\)) such that every vertex of color \\(i\\) has a neighbor of color \\(i + 1 (\\text{mod} k)\\). \\(C_5\\) shows that \\(k\\) may have to be greater than the chromatic number. However, if the graph is connected, infinite and locally finite, and has finite chromatic number, then the \\(k\\)-coloring exists for every \\(k \\geq \\chi(G)\\). In fact, the \\(k\\)-coloring can be chosen such that every vertex is a starting vertex of an infinite path such that the color increases by \\(1 (\\text{mod} k)\\) along each edge. The method is based on the circular chromatic number \\(\\chi c(G)\\). In particular, we verify the above conjecture for all connected graphs whose circular chromatic number equals the chromatic number.","type":"string"},"datatype":"string"},"type":"statement","id":"Q540082$F2B367A5-692C-40E9-83F0-69ACDC1BB3AF","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540082$C01634FF-58D6-4358-BDCB-CFC191441279","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9729428b7f3faff6f70db9a7fa765e75946ff6b6","datavalue":{"value":"05C63","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540082$F1177DD4-6E42-4C80-9705-F6D4E5D9974C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"91bffccf91eb259a938a4565fd0f6d30380e5856","datavalue":{"value":"5903016","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540082$CFE88FF7-F264-4690-8CED-C051FF9D616C","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q540082$04842425-171E-4FAD-B08B-4A5C38903250","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"4f559884bc843cc26aa3de0bf8dccb7937891b29","datavalue":{"value":"circular coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q540082$F366802D-BC5F-428F-8DEE-9C68B843BC65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d7740089849c4786bbd095fc898acf26d17e3722","datavalue":{"value":"rainbow path","type":"string"},"datatype":"string"},"type":"statement","id":"Q540082$73AF8C2D-7EE8-400A-AE9B-40C725451C0F","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":"Q540082$8AF66005-DC29-4328-BF16-806CBF0223F8","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"416126479cfda1488e5ab12f1fd96d246e2bfe50","datavalue":{"value":"bafkreies6bhcdzfphehvbmf45mdzcibpbtlwrntkrmjeyqsxhmlcmjnxaa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q540082$495DCD0C-3C23-4476-9EEE-5F1719C6C421","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d958111e4588f90e575b5932b45c07d20ff57924","datavalue":{"value":{"entity-type":"item","numeric-id":2409512,"id":"Q2409512"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"403c3c777776eaca9e701e957aa93fe766c1cdc3","datavalue":{"value":{"amount":"+0.8571934700012207","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":"Q540082$E93E97B9-B11F-4853-B843-C39905F32AEA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ac4e8009cd2f51b2fc26d3b8aeda8ea7f8670da6","datavalue":{"value":{"entity-type":"item","numeric-id":512581,"id":"Q512581"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"45debb5e1e8f579884e5430dce35eec1371e5132","datavalue":{"value":{"amount":"+0.8440734148025513","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":"Q540082$B40806D7-244C-40CF-AF5D-6AE289BC67AC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e412aff16d0cbaf363fd0e5848e8b48806cbe71f","datavalue":{"value":{"entity-type":"item","numeric-id":625379,"id":"Q625379"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c4622a297f523d431eb8e8c092618c1a1248f0f1","datavalue":{"value":{"amount":"+0.8303027749061584","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":"Q540082$06A6C0B3-7A63-47D7-AE42-8243B5102F5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"e76432e9cf36eb8c89ff42353750afd9fa16547b","datavalue":{"value":{"entity-type":"item","numeric-id":2828929,"id":"Q2828929"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"26629270d703dcb8ae0b6a102d7eae9b27373066","datavalue":{"value":{"amount":"+0.8223230838775635","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":"Q540082$D7AA177A-36CF-4FCB-A968-69B0197A8861","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"92eb4ef4a9a40b23d435545a10897beb93407a51","datavalue":{"value":{"entity-type":"item","numeric-id":3832596,"id":"Q3832596"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e4de75a02443499e15c1f47be64606d41346d54e","datavalue":{"value":{"amount":"+0.8100219964981079","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":"Q540082$BAF69E51-2F95-4168-9CA1-E45C06C6778F","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Rainbow paths with prescribed ends","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Rainbow_paths_with_prescribed_ends"}}}}}