{"entities":{"Q2138972":{"pageid":2149715,"ns":120,"title":"Item:Q2138972","lastrevid":54319610,"modified":"2026-01-26T15:24:35Z","type":"item","id":"Q2138972","labels":{"en":{"language":"en","value":"Vertex-disjoint rainbow cycles in edge-colored graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 7527690"}},"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":"Q2138972$01261BCE-9BAF-480A-AA01-FA793B136366","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"fa99c7dec3262912678bcd6cc67079aad603c000","datavalue":{"value":{"text":"Vertex-disjoint rainbow cycles in edge-colored graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2138972$749E2FAC-458F-4967-9C28-0CC5A73CCA12","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"fc9d8f2c4e39361c3e61046dce64c9f718652d73","datavalue":{"value":"1491.05084","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138972$9D762BD7-67E5-4475-92E8-EEDA85792AE4","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"2da54045dc35dfb221dd6ccca455b6b833741e82","datavalue":{"value":{"entity-type":"item","numeric-id":279397,"id":"Q279397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$BD6B052B-B88B-453E-8E2B-7EEEB216DEAF","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":"Q2138972$51C74BBE-86EF-4CE2-9D83-29B22FE8AD2D","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":"Q2138972$3B626023-CBEE-4F38-AEB3-4149EE5A956C","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"a56af58cfd4d3b017f8833425a5cd2b6e7283d16","datavalue":{"value":{"time":"+2022-05-17T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2138972$0FC9343B-26EA-4951-AFAD-B35530C8DE06","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"b7341ee62c69a0361cf3c8645a9a8801ace721dc","datavalue":{"value":"The existence of cycles, e.g. Hamiltonian cycles or cycles of a fixed length, in graphs (and directed cycles in digraphs) is a well-studied topic, containing classic results such as Dirac's theorem. Related to this, one can also wonder about sufficient conditions for a coloured graph to have a rainbow cycle, i.e. a cycle whose vertices or edges all have different colours.  The authors of this paper consider a version of a problem in this direction.  Let \\(G\\) be an edge-colored graph of order \\(n\\). Then there exists a smallest function \\(f(n)\\) such that if every pair of vertices \\((u,v)\\) together see at least \\(f(n)\\) colours, i.e. the union of their color-neighborhood is at least \\(f(n)\\), then the graph \\(G\\) necessarily contains a rainbow cycle.  In this paper, it is proved that \\(f(n) \\le \\lfloor \\frac n2 \\rfloor\\). The analog of this problem where one is interested in having \\(k\\) vertex-disjoint rainbow cycles, is also considered.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138972$F371FA68-6D7A-4D6B-B31D-5EFF5D0459D5","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"9ea4d24f04e3dffb4771216003ffd35c847cbe39","datavalue":{"value":{"entity-type":"item","numeric-id":820841,"id":"Q820841"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$D9ECEEB7-4663-412B-8750-21216904A712","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138972$F8DCFD2A-F750-4EFD-A7EE-B89DD8EB3951","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138972$26404AF4-AA1E-44C4-A0A7-DE4F06D998A5","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"d916be2c32b1e5042ded78bee8a91e94dc5983d3","datavalue":{"value":"7527690","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138972$9BCCBB03-3B5E-4A3F-85E1-922E959D302B","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"16b0b14615050195933c50b91405fa4d1652e9dc","datavalue":{"value":"edge-colored graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138972$27C2A3B6-FC97-402F-90C3-B867D7B50594","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b0bce5231b7787bc9f0850c9a72716a9802b3167","datavalue":{"value":"color-neighborhood","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138972$D301AFEB-F7D1-4778-9518-96FD125E9406","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"972904ee8c995e9c08b1898fb52a027588eac8ba","datavalue":{"value":"vertex-disjoint cycles","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138972$A3978F86-F312-4CAC-9EE6-7436F57ECCF9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a2ea6fe6bc616e0a77c4ee3bcf836a48dcf505ff","datavalue":{"value":"rainbow cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q2138972$0CAA7933-0636-451C-AADF-6621C4BEF004","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":"Q2138972$CC87D438-1813-44EE-83DB-3CB9024E107A","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"a2bbd2e72b032fae826fba1534a20d4e617e818e","datavalue":{"value":"https://doi.org/10.1016/j.disc.2022.112878","type":"string"},"datatype":"url"},"type":"statement","id":"Q2138972$550A5F32-8339-494E-AE7B-E573BC1BAF64","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"ee94916b73c9ce3260365f19e066cc044bcee53a","datavalue":{"value":"W4220847153","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138972$44525E20-BB83-4D8F-84FD-C4B436C422B3","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"02a7d6450578c42798c24e58bd570344d17cdc3c","datavalue":{"value":{"entity-type":"item","numeric-id":3299210,"id":"Q3299210"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$714F5771-04DB-4014-861D-E69106B289A6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1579d0bf7d86db612ce5a0a497b6a352020ed934","datavalue":{"value":{"entity-type":"item","numeric-id":5205389,"id":"Q5205389"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$4B68895F-95BC-4536-9830-7C1E0865EF0E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2481155a42676d821e036db9e722c8d7abd317aa","datavalue":{"value":{"entity-type":"item","numeric-id":5502988,"id":"Q5502988"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$AD2E4B94-D7F4-4DF4-A609-1E67D8BE291B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0b3d018f710168a4c0bbc22dd78d95193c542bca","datavalue":{"value":{"entity-type":"item","numeric-id":3907591,"id":"Q3907591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$3D29125D-AACB-4654-A7F1-C99FC93EAF45","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$0C390371-7E4E-4762-81BD-7051116A3A80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3814a7a7b63d1c60f6a931870f0151d1753b26f1","datavalue":{"value":{"entity-type":"item","numeric-id":1637139,"id":"Q1637139"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$6618EC5A-ED6B-41EB-8C23-C6157511E968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7b82631da6917417897f9de979a35be56476ede5","datavalue":{"value":{"entity-type":"item","numeric-id":4192089,"id":"Q4192089"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$C2331DC6-8CE6-4E26-8D7D-E5B0CE311FD2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6641226b2796887834e180fe1d0f58ecaa688f55","datavalue":{"value":{"entity-type":"item","numeric-id":906488,"id":"Q906488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$F25AB8BB-0576-4D4E-8E07-28617FB5F702","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"3919ce4b8a7a8565b7eb8b6b9751a8fef7a73ba5","datavalue":{"value":{"entity-type":"item","numeric-id":2662803,"id":"Q2662803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$859CBD8E-BF03-44A8-97E6-9F51D3F624D8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"0be12142d2d66a279c69d6503bbe383ade18e090","datavalue":{"value":{"entity-type":"item","numeric-id":2011150,"id":"Q2011150"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$7C279D84-A59C-4A34-9EEF-0E70F96835EF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2cecb3e4cfa1e3a77dab7e780af7bb189c277e4c","datavalue":{"value":{"entity-type":"item","numeric-id":2421861,"id":"Q2421861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$098FEBA6-0098-456B-9EE9-33BE9710EB22","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f03016ea4656f96ac06f7b528bbfa0c24b13a726","datavalue":{"value":{"entity-type":"item","numeric-id":2910944,"id":"Q2910944"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$0E4A6137-FAE9-4F94-BF40-020AB01C6F9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ab1c5ae27f5067167ba4c4f6b132ee8ad975873c","datavalue":{"value":{"entity-type":"item","numeric-id":2441651,"id":"Q2441651"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$3E4A6A2C-F060-4F60-9557-DAC4D11705FA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a28776ffccf43f90d878cdce75d8399355d78bde","datavalue":{"value":{"entity-type":"item","numeric-id":449221,"id":"Q449221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$99093657-041E-4347-9E20-FE5205A2015C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a106f3b29285f47b1a5047cd0c0cc9194cce8955","datavalue":{"value":{"entity-type":"item","numeric-id":343757,"id":"Q343757"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$EAE962D9-72C1-48E2-B2F0-C47054E75E7B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"055c6a0668b3774173e11a54fec3648a8b71e3e9","datavalue":{"value":{"entity-type":"item","numeric-id":2935291,"id":"Q2935291"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$0FD86B40-2579-43A1-8349-8CB2DBDC201A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"be5163db785afefa7612ea47846a36d75ca95a79","datavalue":{"value":{"entity-type":"item","numeric-id":3563954,"id":"Q3563954"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$A170C006-092D-4612-9119-9099B58EC5DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c574daef71ea19d1319580588b9bbea11bf87489","datavalue":{"value":{"entity-type":"item","numeric-id":5857005,"id":"Q5857005"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$CB111B41-2EBA-4CC4-A0EE-0C8D0D2AB2C2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"354a350a19b7f023b6db0fa371461b95e5edb9c6","datavalue":{"value":{"entity-type":"item","numeric-id":595675,"id":"Q595675"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2138972$3C521E22-401D-4636-9AFD-BDC01BF49D1E","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"c26e63112661aba5312bf5ce08917e1261988062","datavalue":{"value":"10.1016/J.DISC.2022.112878","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2138972$B8905227-72E0-46E6-A630-27D9C289CC41","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01a9472136d4624586c1cbc9f6ef588f3e339d23","datavalue":{"value":{"entity-type":"item","numeric-id":2675843,"id":"Q2675843"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7c73980ac1f3e1c6ba91b2c1d5d8b0417e16aecd","datavalue":{"value":{"amount":"+0.869564414024353","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":"Q2138972$B6FD62BA-B255-43B4-AF31-229252E5E7CC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8eb9dcb0aba63fbcb7c4a32bff8e957674fcc130","datavalue":{"value":{"entity-type":"item","numeric-id":2005705,"id":"Q2005705"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83b5a663a3d1fd5fe885c742d37ad96e8ccc93d8","datavalue":{"value":{"amount":"+0.8603830337524414","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":"Q2138972$8995C264-B716-4F3C-A98A-5C514F50FD5E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"5f566eb7ff4adb90496ddb5f20665835bd52f3af","datavalue":{"value":{"entity-type":"item","numeric-id":2421861,"id":"Q2421861"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"8d05b48fe43fd5fd49c31675247f8d627e664b4a","datavalue":{"value":{"amount":"+0.8531913161277771","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":"Q2138972$0F42879A-6C87-4FFD-BE2F-406736FD4072","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"382870a9f3bc0157eccafba2f690759887cdd4aa","datavalue":{"value":{"entity-type":"item","numeric-id":906488,"id":"Q906488"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f4bb6163f378cea8e10c18c85d849c97ad391383","datavalue":{"value":{"amount":"+0.8465995788574219","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":"Q2138972$DB332493-ECAC-49A3-8D64-3204B414856E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6e7017e7433946089eccd95d02c66e29ff6bf965","datavalue":{"value":{"entity-type":"item","numeric-id":2662803,"id":"Q2662803"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c9c9fe48175a0d3ba97cb7046e2c8c0823389371","datavalue":{"value":{"amount":"+0.8445874452590942","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":"Q2138972$D9414A0F-47AE-4197-8A55-276061767ADB","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2138972","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2138972"}}}}}