{"entities":{"Q2401439":{"pageid":2412182,"ns":120,"title":"Item:Q2401439","lastrevid":74305134,"modified":"2026-04-14T19:27:01Z","type":"item","id":"Q2401439","labels":{"en":{"language":"en","value":"Large monochromatic components in edge colored graphs with a minimum degree condition"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6772926"}},"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":"Q2401439$D1CE23AB-60B9-4041-B75A-0886687C010A","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c27c1011eec43ac064823584fc28dcd57f2f91fd","datavalue":{"value":{"text":"Large monochromatic components in edge colored graphs with a minimum degree condition","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2401439$7AEB432F-F77D-4306-BA88-62B5889448D3","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7a7fc871de80ebff567d87187512b8b47544ff75","datavalue":{"value":"1369.05076","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2401439$9438B5B6-71D6-4B82-8BB3-AB4F73885777","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"e2f3fdbf9f8c798d03777e6ed3c1ca10e41eb29d","datavalue":{"value":{"entity-type":"item","numeric-id":190556,"id":"Q190556"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$C8D79B82-BE44-4171-8D74-F2ABF54F3836","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":"Q2401439$EB329901-4130-4EB5-94C5-036DEF82F60C","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":"Q2401439$9745B91E-ECE4-4774-9347-24A47782EA20","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"c67d8078e1a5d9d2033371c1c5369954e233b550","datavalue":{"value":{"time":"+2017-09-08T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q2401439$9DDE5DE0-F524-4C6A-B67D-A8523B78C44E","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"8400e36c33bb3facc45caa24762013f4c3c35d61","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p54","type":"string"},"datatype":"url"},"type":"statement","id":"Q2401439$2BE81634-F582-4B2D-8C6C-FED279B10CF9","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"40c81853bb210b06b31139359018ba64bda7c95a","datavalue":{"value":"Summary: It is well-known that in every \\(k\\)-coloring of the edges of the complete graph \\(K_n\\) there is a monochromatic connected component of order at least \\(\\frac{n}{k-1}\\). In this paper we study an extension of this problem by replacing complete graphs by graphs of large minimum degree. For \\(k=2\\) the authors proved that \\(\\delta(G)\\geq\\frac{3n}{4}\\) ensures a monochromatic connected component with at least \\(\\delta(G)+1\\) vertices in every \\(2\\)-coloring of the edges of a graph \\(G\\) with \\(n\\) vertices. This result is sharp, thus for \\(k=2\\) we really need a complete graph to guarantee that one of the colors has a monochromatic connected spanning subgraph. Our main result here is that for larger values of \\(k\\) the situation is different, graphs of minimum degree \\((1-\\epsilon_k)n\\) can replace complete graphs and still there is a monochromatic connected component of order at least \\(\\frac{n}{k-1}\\), in fact  \\[ \\delta(G)\\geq \\left(1 - \\frac{1}{1000(k-1)^9}\\right)n \\]  suffices.{  }Our second result is an improvement of this bound for \\(k=3\\). If the edges of \\(G\\) with \\(\\delta(G)\\geq \\frac{9n}{10}\\) are \\(3\\)-colored, then there is a monochromatic component of order at least \\(\\frac{n}{2}\\). We conjecture that this can be improved to \\(\\frac{7n}{9}\\) and for general \\(k\\) we conjecture the following: if \\(k\\geq 3\\) and \\(G\\) is a graph of order \\(n\\) such that \\(\\delta(G)\\geq \\left(1-\\frac{k-1}{k^2}\\right)n\\), then in any \\(k\\)-coloring of the edges of \\(G\\) there is a monochromatic connected component of order at least \\(\\frac{n}{k-1}\\).","type":"string"},"datatype":"string"},"type":"statement","id":"Q2401439$272B5AB2-6A30-4134-BC00-2A082145D3AB","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2401439$11C50746-327F-42C3-8D44-3AEB137C6B86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2401439$75FBCD91-9508-43A8-8C8E-1DDFE091F08A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2401439$05DBD163-B7FA-4C51-941C-FCFE81F81D68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"9b4b251e34f965e85a4a30c5d646e0bae1192967","datavalue":{"value":"05D10","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2401439$726F7524-1CC1-4092-9954-74FD0890DF84","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"4bb87cb7cb78e1c63330d5910c7e57d80f51f362","datavalue":{"value":"6772926","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2401439$C1B46ECB-E435-4AF5-AA09-69302DE944B0","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"88f9e038ce90ce67b356cbe14c3c3f15dfb789be","datavalue":{"value":"Ramsey theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q2401439$CDC5915F-310D-40A4-AB81-095BEF2C1B35","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"84f71be9fca46fd3657c068e721360ac552458d2","datavalue":{"value":"monochromatic components","type":"string"},"datatype":"string"},"type":"statement","id":"Q2401439$2C46CEA2-CD94-4CF2-970A-66617D424631","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":"Q2401439$30AF2830-904D-4845-9180-DCFE776FA255","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"98e2393a7988f84c97e289af1cf2ecaa78f00b38","datavalue":{"value":{"entity-type":"item","numeric-id":510329,"id":"Q510329"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$CC15508C-BC6A-4BB6-8D02-854D6222EDA9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2f09c8481368e80a5a599494375a1fd46d6c6b91","datavalue":{"value":{"entity-type":"item","numeric-id":484546,"id":"Q484546"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$4014BE7A-3B22-4DAF-A552-CB7AFB7379A1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9d6c5de41d0bdbb1cf60b306059f267fb26b1c99","datavalue":{"value":{"entity-type":"item","numeric-id":2800590,"id":"Q2800590"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$2D35203D-A9FA-48A0-A714-D4AA1ED5C924","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b74cfe5e994854e464f5352705dede69ca695bb7","datavalue":{"value":{"entity-type":"item","numeric-id":2883852,"id":"Q2883852"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$7A3A1CD5-6957-4616-82EF-2BE750EBC895","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9a579eb7f2df2dfcfcee5483831d2809bfb4da64","datavalue":{"value":{"entity-type":"item","numeric-id":345114,"id":"Q345114"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$8C8128A8-9D71-4596-BCE1-D85271D03260","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ec6372aa5083c513a696ae3bc2ecfc96225c9624","datavalue":{"value":{"entity-type":"item","numeric-id":5357963,"id":"Q5357963"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$C96285C4-AB0A-4764-8D37-54A20B6C1DE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763b9af23bb58474b60bc92c769991eb74987ad9","datavalue":{"value":{"entity-type":"item","numeric-id":3064179,"id":"Q3064179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$41EF3C84-3E28-412C-9134-FD3F3D864D80","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"59da1746ab78ce390d72a6439934b21f9b429e6c","datavalue":{"value":{"entity-type":"item","numeric-id":2883860,"id":"Q2883860"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$AB8738EA-E3DE-4D9A-85C9-6EA9E61274E8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8c7d93ddb982376b0ebbecfddc49e3e29c9816df","datavalue":{"value":{"entity-type":"item","numeric-id":4240605,"id":"Q4240605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$A553C0C6-1044-406F-91CB-910D4E8A036C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b46772429aa53b7b7399a5796624f2fe6aecb2e2","datavalue":{"value":{"entity-type":"item","numeric-id":3067062,"id":"Q3067062"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$ABBF42F0-641A-4FB4-AB56-D19AAA10683F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"922598857b64c682415741da5fd4eb7cb848d71b","datavalue":{"value":{"entity-type":"item","numeric-id":4200109,"id":"Q4200109"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$BD3B3830-63A7-484C-A6C8-26073896F164","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1c8660a88fb3a5014a5202c9b85e613e205ab4ad","datavalue":{"value":{"entity-type":"item","numeric-id":5272638,"id":"Q5272638"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2401439$117128E6-F552-45FD-B1EE-04198E39D9EF","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"991d5481c6e0ef7840e6476e9e11cdb624f16655","datavalue":{"value":"bafkreidf3haeyukbi5zvgqcl5jj7ixlruej7vuyaai6cjv53dhuheseu5q","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2401439$0E0DF9DC-4D72-42ED-925A-99A3357FCCC3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2df4104f719c780cd9394e97a9f404990c613585","datavalue":{"value":{"entity-type":"item","numeric-id":2223462,"id":"Q2223462"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ffcb499ded2d51f7d3a9cc378ce393d4e7731cb4","datavalue":{"value":{"amount":"+0.98653865","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$B7D583E6-B1D2-498D-8DCE-D4CD7F957507","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"78960e9c15fc4fd7e3813ec077f9b6d397780334","datavalue":{"value":{"entity-type":"item","numeric-id":3064179,"id":"Q3064179"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9555a77b34878f14c43d7476bcf2dca1564b4aa3","datavalue":{"value":{"amount":"+0.9631731","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$949DA1FD-F5BE-4D10-B2B8-724794575B2F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9f0dccfd428b2c8e915ec6f77abc708c827b8a04","datavalue":{"value":{"entity-type":"item","numeric-id":5110681,"id":"Q5110681"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"415a889b9631fe9f5f8be4d721e31fbd666fe8bb","datavalue":{"value":{"amount":"+0.9392761","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$F1BFFF35-C243-447B-AC82-A8A04B25597A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8dba62cbf366c5976f21fd679874efc07b9b2a3c","datavalue":{"value":{"entity-type":"item","numeric-id":2034067,"id":"Q2034067"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"d0c3adb89a76193aa712362238ede6735a903dd7","datavalue":{"value":{"amount":"+0.9348966","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$A0A32EE0-14A0-4DDC-8862-749C8077B088","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"2a4cec68f0fdc4fea5c4f8aa8f8272ca59c3825e","datavalue":{"value":{"entity-type":"item","numeric-id":778694,"id":"Q778694"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ba6700e943ec8bd7a6dc888affe48831eb4560fb","datavalue":{"value":{"amount":"+0.92619616","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$0C1891C9-40EF-4358-858E-149E1348B0F0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"07fe582b35efdff5467fdabcf5ff53e6b42d1d96","datavalue":{"value":{"entity-type":"item","numeric-id":2092426,"id":"Q2092426"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"3e1a2b03fd4638657821eb7b874f031b49318f2c","datavalue":{"value":{"amount":"+0.9143055","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$3C375DE0-0930-477D-8CFC-A0B24BBE76E9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed55cf4daee770efccdbd492811b4211842feb55","datavalue":{"value":{"entity-type":"item","numeric-id":2442266,"id":"Q2442266"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7e6a87e1cddf12e15150d3b7053d0838ff292a51","datavalue":{"value":{"amount":"+0.91306293","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$9C9BFDA5-10F5-42C4-8DF0-37516C4B27E7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"51c08640db0091cd975bc0297d3df181de481723","datavalue":{"value":{"entity-type":"item","numeric-id":2857398,"id":"Q2857398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cd3725ddf30c1730a79383d7c3843e55806cbae","datavalue":{"value":{"amount":"+0.91223264","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$0447B822-3244-4CCE-865E-394FD379C82F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8fe84203791d92f840ce3416f51ace8d375196cb","datavalue":{"value":{"entity-type":"item","numeric-id":2509763,"id":"Q2509763"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2cd3725ddf30c1730a79383d7c3843e55806cbae","datavalue":{"value":{"amount":"+0.91223264","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ac3c626774dcd0d16f89557f66586245841a01db","datavalue":{"value":{"entity-type":"item","numeric-id":6767936,"id":"Q6767936"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2401439$20890695-92CE-4E04-958A-2DBDFD40932D","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Large monochromatic components in edge colored graphs with a minimum degree condition","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Large_monochromatic_components_in_edge_colored_graphs_with_a_minimum_degree_condition"}}}}}