{"entities":{"Q456358":{"pageid":458125,"ns":120,"title":"Item:Q456358","lastrevid":51581369,"modified":"2026-01-18T21:34:12Z","type":"item","id":"Q456358","labels":{"en":{"language":"en","value":"Partition of graphs and hypergraphs into monochromatic connected parts"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6098369"}},"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":"Q456358$11F8222C-DC9B-435D-8D94-20BF6EC7F70D","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"08b13a68e3de107da99c10c6a34206e13e6e3a61","datavalue":{"value":{"text":"Partition of graphs and hypergraphs into monochromatic connected parts","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q456358$F5309BA6-9441-4E7F-B624-D444CC0F008D","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"d5598ebf7920121073d92bcdef21b62f6155a10e","datavalue":{"value":"1252.05176","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456358$D32C07EA-CB17-4CEA-9143-00C037307FA2","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"8be7c510457dea74e91b46714dd152d97da1e670","datavalue":{"value":{"entity-type":"item","numeric-id":323045,"id":"Q323045"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456358$D3BD0A73-6EF2-4CFF-B204-B5943C3E8C5F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2fea587b0b8abc947c30ceac0aa37e4e6b46ed6e","datavalue":{"value":{"entity-type":"item","numeric-id":343720,"id":"Q343720"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456358$E4621EED-34BA-4B3F-A642-E3C85CB8D0E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"3155ff163c931be8945149a68c11d68da0b397d6","datavalue":{"value":{"entity-type":"item","numeric-id":228779,"id":"Q228779"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456358$84F19DDB-5D63-4FD7-8C6B-92D0C8EBF9DE","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bab56afd105f46e142fe49dbbf4bce2482b5764b","datavalue":{"value":{"entity-type":"item","numeric-id":405233,"id":"Q405233"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q456358$6A702489-EB2B-4E40-BDBE-43938ABED964","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":"Q456358$CA0C111A-E4BB-4BF9-ABDE-B86368AC7C71","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"6ee92d50481ed05c06549abf63f6ece88b90dd74","datavalue":{"value":{"time":"+2012-10-24T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q456358$D487CD84-CD7B-43F7-BE2A-5C8A92F7BF73","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"df4ffad8b0b35209cdb8cd4c9b64fffd660155de","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v19i3p27","type":"string"},"datatype":"url"},"type":"statement","id":"Q456358$F70A41E8-FA34-4F0A-A504-FC650974FF06","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"52df41b4d9db344896d2565ca8eda56c0f66c89e","datavalue":{"value":"Summary: We show that two results on covering of edge colored graphs by monochromatic connected parts can be extended to partitioning. We prove that for any 2-edge-colored non-trivial \\(r\\)-uniform hypergraph \\(H\\), the vertex set can be partitioned into at most \\(\\alpha (H)-r+2\\) monochromatic connected parts, where \\(\\alpha (H)\\) is the maximum number of vertices that does not contain any edge.    In particular, any 2-edge-colored graph \\(G\\) can be partitioned into \\(\\alpha(G)\\) monochromatic connected parts, where \\(\\alpha (G)\\) denotes the independence number of \\(G\\). This extends K\u00f6nig's theorem, a special case of Ryser's conjecture. Our second result is about Gallai-colorings, i.e. edge-colorings of graphs without 3-edge-colored triangles. We show that for any Gallai-coloring of a graph \\(G\\), the vertex set of \\(G\\) can be partitioned into monochromatic connected parts, where the number of parts depends only on \\(\\alpha(G)\\). This extends its cover-version proved earlier by Simonyi and two of the authors.","type":"string"},"datatype":"string"},"type":"statement","id":"Q456358$1A082E4E-21C7-4327-810A-31AEC76C578C","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"625e55f1f2a96178239720bc1bbbe7ad21cf0a75","datavalue":{"value":"05C70","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456358$D5CC4EFF-5EB4-4714-AAAC-D904B33C8817","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456358$8C0E902E-EE7A-408E-8521-40F269EB5177","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"c6a3478e468d1d1945edd49f8b7c65462e4b4e22","datavalue":{"value":"6098369","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456358$E57A3664-08E4-4D19-B7BF-47C284EAA349","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"0bc0aacc91b972b37126e5e988317d66de065666","datavalue":{"value":"covering of edge colored graphs by monochromatic connected parts","type":"string"},"datatype":"string"},"type":"statement","id":"Q456358$D58318A6-2CEB-4577-BB5A-DBE317577BF6","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":"Q456358$0BA7FAEA-A6A4-4D02-B6DE-A433CE6A4C8F","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"b565c9eb37c3ffa86dbb0f041186692bed4e26a1","datavalue":{"value":"bafkreihg2474y7cd6cg6dxngwyxelhwa2xyjltu32ifomkedn6r3by6ssa","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q456358$8A4C5D4A-7757-492D-A24C-AAA6B85D22FF","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"3f91c21fb12aa8e68e44f2237fdf7e5bffe67e52","datavalue":{"value":{"entity-type":"item","numeric-id":2404363,"id":"Q2404363"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b4be21b5a03a05112f2236803cd87ab6a2bb9e8d","datavalue":{"value":{"amount":"+0.8438987731933594","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":"Q456358$473C0712-8229-4444-AE64-1C88D211A7E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"77443d1e3248625fc9109095d5755df7f2f0e726","datavalue":{"value":{"entity-type":"item","numeric-id":405234,"id":"Q405234"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e3ddf0fd9a7e486294a17e70b9d085e83e1e823","datavalue":{"value":{"amount":"+0.839213490486145","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":"Q456358$55434201-0910-4673-9A65-F32579BE9A0D","rank":"normal"},{"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":"5f176f79509f0d0df582f526c06842a63b0ffe7f","datavalue":{"value":{"amount":"+0.8375957608222961","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":"Q456358$74815B22-F239-463E-A4FB-2784076D11B4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"45d9e6c59db6817e133aae329a595a62f470de0d","datavalue":{"value":{"entity-type":"item","numeric-id":5854893,"id":"Q5854893"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"67f6351c758c882bf4c5e7b2e5c201dff5741f35","datavalue":{"value":{"amount":"+0.8341204524040222","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":"Q456358$0CC5F054-CC25-4911-A898-60296FD428E2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"986733d0f2b974da542f966e7089b0a8754d6ff8","datavalue":{"value":{"entity-type":"item","numeric-id":3067062,"id":"Q3067062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"c0ec191e11824429bf849eb9efb84edccc5dfda9","datavalue":{"value":{"amount":"+0.8300999402999878","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":"Q456358$87B7F613-3E33-4886-B4A3-639352AF4B70","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:456358","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:456358"}}}}}