{"entities":{"Q949751":{"pageid":951599,"ns":120,"title":"Item:Q949751","lastrevid":65610624,"modified":"2026-04-12T03:46:54Z","type":"item","id":"Q949751","labels":{"en":{"language":"en","value":"Colored graphs without colorful cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5355063"}},"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":"Q949751$021EF9B1-0DDE-430D-981E-CF6019F0558C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"d66c81038faf8816950f3bd47590389ab96a6a78","datavalue":{"value":{"text":"Colored graphs without colorful cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q949751$52819F64-10D5-4C57-8AEF-3975B35964D9","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"5f6cd3ac2b2d6ad22c873e9f63520816b57253b5","datavalue":{"value":"1174.05041","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949751$3472979C-2E7B-4360-90B2-776DC638E876","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8978c34b34784de614de4ef62e5765f7a01a8e21","datavalue":{"value":{"entity-type":"item","numeric-id":283253,"id":"Q283253"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$64BDFEBD-85BE-41B9-89FB-B5B83A06D4CF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfc8aa2d9e06e17cf9a1d90aa11cebea15cb833e","datavalue":{"value":{"entity-type":"item","numeric-id":949750,"id":"Q949750"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$1C3A6219-C5D1-4824-BCC0-6706E17EA4F6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"f2ec4988b2740deb3f4f56ca53450b3e354afa7e","datavalue":{"value":{"entity-type":"item","numeric-id":1141149,"id":"Q1141149"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$AF0BC99E-14ED-4D2B-B16A-C1E4DC89B73C","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"a87e84d22579e69c48ca0a6d828473db4dde3dd6","datavalue":{"value":{"entity-type":"item","numeric-id":168579,"id":"Q168579"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$236ADBAE-20A2-4D82-A76A-D6C73008B83E","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"5b4a05105c8454225903df775b1ba3fdbda7455a","datavalue":{"value":{"time":"+2008-10-21T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q949751$0EB3EE0A-C7B1-4562-9906-04746504B8D3","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"c179b712c680151bc4a3cce35f0a6e3a1b085fa1","datavalue":{"value":"https://arxiv.org/abs/1509.05621","type":"string"},"datatype":"url"},"type":"statement","id":"Q949751$33C4ACE6-D480-4D71-AB8D-4E88BD6AEFE0","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"58d6ba558d389b15ec9b3b0187b1458b6fb39856","datavalue":{"value":"A cycle in a complete graph with coloured edges is called colourful if each of its edges has a different colour (such a subgraphs are sometimes called rainbow as well). It is shown that complete graphs with coloured edges do not have colourful cycles if and only if they are so-called Gallai graphs, i.e. graphs that do not possess colourful triangles. It is shown that the ommited edges of colourful cycles with the operation \\(m\\circ n = m+n-2\\) form a monoid.  The authors provide a characterisation of Gallai graphs and two characterization of the connected components of maximal monochromatic subgraphs of exact Gallai graphs. The characterizations of maximal monochromatic subgraphs are given in terms of full homomorphism and homomorphisms duality.","type":"string"},"datatype":"string"},"type":"statement","id":"Q949751$4C78E2DE-9EA1-4FA4-BB5F-9B43ED3C22CB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949751$4DF26261-5EB6-42A9-94F3-63466D3F272E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949751$37A5EA70-F3B4-43E8-A0C1-D4FD7E3EB63B","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"633a8e3a134b8b346b511a0eeea9de02879e3b2a","datavalue":{"value":"5355063","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949751$653CCBB5-FD4C-4BBF-975C-7890B159C24E","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"e3fa6361f24f48960e1e8dcb92e2c7d847982628","datavalue":{"value":"colourful cycle","type":"string"},"datatype":"string"},"type":"statement","id":"Q949751$0DBA6DAA-3D60-41D5-8007-B75FCBE9BAFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b4c0d988d3c7eb4a9a38e62adf2101cda37170c4","datavalue":{"value":"rainbow colouring","type":"string"},"datatype":"string"},"type":"statement","id":"Q949751$79B56628-7E7E-40AC-8AC9-C43DD6CD13EE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"c05700fecc0f5b5fec30e5312e225aca0bf62460","datavalue":{"value":"monoid","type":"string"},"datatype":"string"},"type":"statement","id":"Q949751$DD7F4074-3912-4663-AA55-F905C30F642C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"191a5fb5dc884ae6ea17bb21c16d0da160897979","datavalue":{"value":"Gallai graph","type":"string"},"datatype":"string"},"type":"statement","id":"Q949751$90447977-B1CB-4917-9A52-DBD601082E39","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"5e636d6200f7544f4dd5a5bbed79f99982c70f6d","datavalue":{"value":"homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q949751$E05A8422-BADB-40AB-909F-EA134A491077","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"af45ac16b5c3b4cb5ad35340a1e807846a86d0e0","datavalue":{"value":{"entity-type":"item","numeric-id":593274,"id":"Q593274"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$9DBC9F5C-40AC-4417-AA80-B63DBCAC750D","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":"Q949751$D322A1F3-2C71-4327-B901-D1551046B01E","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"799d0aeafa1edb3abf4acd03603028475ec328f3","datavalue":{"value":"W2036460087","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949751$A2A19941-CA1D-4CE0-9753-6E9C57981E39","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"1efd51fcd8df11062a63f8e4bf25d8f9694b70c6","datavalue":{"value":{"entity-type":"item","numeric-id":870025,"id":"Q870025"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$28B6E54D-6DC9-41EF-9A52-9D0BFB8388E3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1306bc361c8b48b4257b020fe0e3667d306d50c4","datavalue":{"value":{"entity-type":"item","numeric-id":4355067,"id":"Q4355067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$2CBB0451-5FF4-459D-8415-B74C80261C0D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"4b079ce3948c710db0cc95452d4f9ac2a3b66861","datavalue":{"value":{"entity-type":"item","numeric-id":787167,"id":"Q787167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$D67AC04A-04CA-4A98-934C-D2C4A020380D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a8539d1fcf3cff5fbb08dd6973662b887ad57892","datavalue":{"value":{"entity-type":"item","numeric-id":5534028,"id":"Q5534028"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$1B31E2D3-8C26-492F-8171-0F7D1E7A1619","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"d8a1ac7066f140cc6e60d1ba409df0fd2e12289f","datavalue":{"value":{"entity-type":"item","numeric-id":4474285,"id":"Q4474285"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$E998B13B-2283-492B-9A3B-8245E9A22608","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f7014eea8e2ba4d9052c08c9e0e557b227a54bc1","datavalue":{"value":{"entity-type":"item","numeric-id":4871773,"id":"Q4871773"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$97D21793-E177-4C59-A88F-9AC86E485B8A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01874425d018f2c41712bb3fb8e538c43c3a3a01","datavalue":{"value":{"entity-type":"item","numeric-id":1250117,"id":"Q1250117"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q949751$EF29480C-7ACE-4585-83F9-25558EC6CED8","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"900bf3bc39f0108e849e69d5a4783245f87de559","datavalue":{"value":"10.1007/S00493-007-2224-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q949751$D91DC6B3-9CC8-46B5-8C8B-3E31B508C472","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a13e4f91d3771137f25850a8abd75c08f64d23b6","datavalue":{"value":{"entity-type":"item","numeric-id":966033,"id":"Q966033"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a037cbab6fd4767b5cc70c1575831d3c8fa9a285","datavalue":{"value":{"amount":"+0.8172005414962769","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":"Q949751$573ED9C7-DD30-41C3-A41E-C3F187468822","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9b264bfdb910b4e31e66d8b7b6560493d7ee9c3a","datavalue":{"value":{"entity-type":"item","numeric-id":2800592,"id":"Q2800592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4299d9140c2989a308583d693f483332e688c926","datavalue":{"value":{"amount":"+0.8166752457618713","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":"Q949751$561D57C0-2C15-4D42-B982-711DA080F3D9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a735671d2c098e882fd9e5ac838c38835de7fba","datavalue":{"value":{"entity-type":"item","numeric-id":2045403,"id":"Q2045403"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"74da82a1e260feee5f746ce2f6480a0047bee4e6","datavalue":{"value":{"amount":"+0.8106376528739929","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":"Q949751$72D17010-75CF-4E26-9844-12CBADCEF29D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"83337a002e76679954d74c3cc2b078f9d6191127","datavalue":{"value":{"entity-type":"item","numeric-id":6056775,"id":"Q6056775"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a0b144d6a55a9b68649cc77f37898058cdba4ed1","datavalue":{"value":{"amount":"+0.8093408346176147","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":"Q949751$BC960D97-3E78-46E5-AF4E-B8C98BA0483F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"cb21058f0f96f8580dd2c8ed61fa43832c3a1ec3","datavalue":{"value":{"entity-type":"item","numeric-id":2450129,"id":"Q2450129"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a1c935996d1d32fbea405f8c19634919b9ffff74","datavalue":{"value":{"amount":"+0.8056603670120239","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":"Q949751$354C05CB-F7FF-48AB-95E9-BE2168641D86","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Colored graphs without colorful cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Colored_graphs_without_colorful_cycles"}}}}}