{"entities":{"Q1354729":{"pageid":1365468,"ns":120,"title":"Item:Q1354729","lastrevid":46735689,"modified":"2025-12-25T12:05:39Z","type":"item","id":"Q1354729","labels":{"en":{"language":"en","value":"A note on alternating cycles in edge-coloured graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 1006760"}},"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":"Q1354729$C69F99F7-994E-4633-932C-306E18C291C9","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"93d1b4419c5656d8c6d793e831619ddec837dcb1","datavalue":{"value":{"text":"A note on alternating cycles in edge-coloured graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1354729$CF3D774B-C2E6-44B6-9581-5038E38AD468","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"aeddcc06305701d4afc5d43b66df48c1ed4f93f4","datavalue":{"value":"0870.05042","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1354729$9AD472EA-D0B8-427C-B086-E383DC7105F8","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"ce446809cda0969b939786a794eae79a100b8b76","datavalue":{"value":{"entity-type":"item","numeric-id":168085,"id":"Q168085"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1354729$C79179ED-955C-4C77-BF30-7DD3E5426DF6","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"f07f6fd6d97bd24ff86249abf8a501d3b63b437d","datavalue":{"value":{"entity-type":"item","numeric-id":256978,"id":"Q256978"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1354729$D32A3A2A-2B1A-4DAA-A06E-67F6A85A409F","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"8eb1335ea3ff8239be65e16ffb01fc1c1358604b","datavalue":{"value":{"time":"+1997-09-15T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1354729$7C4F7961-7F4C-47CB-AFB4-3219D227559F","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"1308c9bc0337e04e173362931e71b652c938d3a1","datavalue":{"value":"https://semanticscholar.org/paper/1abc9330ef7b648fd6704e98c2ab5349023f6a90","type":"string"},"datatype":"url"},"type":"statement","id":"Q1354729$813FDFB1-FD7E-4B40-A9BE-B1A5B4AADB3B","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"5f191deecb4a9b0b088f27b850a134fb86db4502","datavalue":{"value":"\\textit{J. W. Grossman} and \\textit{R. H\u00e4ggkvist} [J. Comb. Theory, Ser. B 34, 77-81 (1983; Zbl 0491.05039)] gave a sufficient condition for a 2-edge-coloured graph to have an alternating cycle (i.e. a cycle with no two consecutive edges of the same colour). In the paper, this sufficient condition is extended to edge-coloured graphs with any number of colours. This allows to verify in polynomial time if an edge-coloured graph has an alternating cycle. For more information on alternating paths and cycles, see \\textit{J. Bang-Jensen} and \\textit{G. Gutin} [Alternating cycles and paths in edge-coloured multigraphs: A survey, Discrete Math. 165-166, 39-60 (1997)].","type":"string"},"datatype":"string"},"type":"statement","id":"Q1354729$158DD396-8D96-4B00-9FF7-A6512E261169","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1354729$0146AB93-0F33-460C-9D04-D3ABC19B564F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1354729$55E1A552-7960-4641-91D8-B095AA7AC09C","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"13be1fd6f11fdd4914288fedbe4b805062529f4f","datavalue":{"value":"1006760","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1354729$58D6FE50-95E4-45CE-B4D8-0125D62EE288","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"7e8f007e77064c5b832103cf974449be847ab653","datavalue":{"value":"alternating cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q1354729$BCEC549D-1492-427B-A3F7-E9920563B56E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2901dd3dffade590a541c6dd91737e0616614b3e","datavalue":{"value":"edge-coloured graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q1354729$8BE570D6-572D-4C33-B2FC-9E6325D1E0D4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"a862f016acc1e519aa7b6644887bfca464692961","datavalue":{"value":"polynomial time","type":"string"},"datatype":"string"},"type":"statement","id":"Q1354729$B7BB4412-C2A5-4C70-9847-96BE15B622CB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"1e865dcf04feef79efcf163ac054d2ac37b7305b","datavalue":{"value":"paths","type":"string"},"datatype":"string"},"type":"statement","id":"Q1354729$5256CB36-35B8-4D5B-93BE-71FD7D900ECA","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"4fefa17be9d4bfc1a51cd1d93e86e23724d8c0a1","datavalue":{"value":{"entity-type":"item","numeric-id":168084,"id":"Q168084"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1354729$FECB47AF-86F2-4B18-8266-CA6FF46E872D","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":"Q1354729$EDDFD119-8D2E-4A5D-999D-5AEB52E0B5AB","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"c2bc4c984558e5ec882c9f5042cd990be568a4b6","datavalue":{"value":"W2079569132","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1354729$FF26FEC4-C2F8-42AB-AE8F-3E9FD7223B84","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1361f6152a68eae1ce1ac7ce0090fde81c4f0d8f","datavalue":{"value":{"entity-type":"item","numeric-id":1356728,"id":"Q1356728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1354729$BB03BA16-581A-4A12-B3C9-483D3FF637AF","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":"Q1354729$9EA61875-AB28-4A4A-8590-8423F3906F91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"824b8359200d9b48d181f9b3373a423923afd941","datavalue":{"value":{"entity-type":"item","numeric-id":1167184,"id":"Q1167184"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1354729$B2A81A80-95FA-459F-9604-FF3452B05FFF","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"04714fec17255342778e9ba7769c317305595c5e","datavalue":{"value":"10.1006/JCTB.1997.1728","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1354729$56FC3CDF-0C01-4248-A362-3B4BBAC0CA82","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f8fbff099c3c0f3dc54d2340fc2c7b10d162e06f","datavalue":{"value":{"entity-type":"item","numeric-id":1356728,"id":"Q1356728"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"49cc46010d99f6cf511b1e7fed29117f7baddaa1","datavalue":{"value":{"amount":"+0.8642956018447876","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":"Q1354729$EFCCB0CC-7F38-4889-A722-39C2BF95BAC6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0c7edab200241e6ced0bd732835f65a925b0cd5c","datavalue":{"value":{"entity-type":"item","numeric-id":1043956,"id":"Q1043956"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"61627a36f18b02fec67ebc11dd3d7cdc0b53e2aa","datavalue":{"value":{"amount":"+0.8603564500808716","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":"Q1354729$F9A468F0-E0DB-4EC8-BEF1-D0A8B26F9360","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2f213077e61558b67c28ba56319c447a11b376c0","datavalue":{"value":{"entity-type":"item","numeric-id":4320687,"id":"Q4320687"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b9a54f83e9909c886f98f641ca34672a38e11da1","datavalue":{"value":{"amount":"+0.853670060634613","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":"Q1354729$CD42CFA9-492B-4265-9786-A13B6223BFAF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:1354729","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:1354729"}}}}}