{"entities":{"Q2870527":{"pageid":2881247,"ns":120,"title":"Item:Q2870527","lastrevid":42364306,"modified":"2025-06-13T03:16:25Z","type":"item","id":"Q2870527","labels":{"en":{"language":"en","value":"Forbidden rainbow subgraphs that force large highly connected monochromatic subgraphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6248059"}},"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":"Q2870527$C93C1B5A-E914-46A5-AD8F-EC153B0D49DF","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"26132044e039c146497f80774146bc123ea2e141","datavalue":{"value":"1310.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870527$B1A18417-B6F3-4481-BFC5-FF2A3792BB48","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"646697c83890193b78c6ab507ffa6e6631cd1008","datavalue":{"value":"10.1137/120896906","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870527$1308B6C4-2B7C-4FB6-9B25-F674E35E15D9","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":"Q2870527$68ACD5F6-506A-4D5C-A551-14D05AB03B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"d915f415c2048da84ab961cd9235204220e76ead","datavalue":{"value":{"entity-type":"item","numeric-id":293605,"id":"Q293605"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870527$F47A36A1-B2C8-40B5-8E48-32C61507ADD4","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"39a509948a5fd41054da3e7af81581f39adaebc1","datavalue":{"value":{"entity-type":"item","numeric-id":2706174,"id":"Q2706174"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870527$9CEC34B4-5635-4A40-A9D6-9E7C7F18C565","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"41a1e4f019ef435c314233e0481265bcc6e79494","datavalue":{"value":{"time":"+2014-01-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":"Q2870527$01AF4709-2C19-49A9-882E-635C0E879860","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870527$9985AEA8-F5CC-4AD8-8ECD-BD28348A6C9D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5554b9c844f173ce8299bcb1bb0c8b42f6b4a0be","datavalue":{"value":"05C40","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870527$34B6FC83-1C5C-4647-B38C-97A9C6CFB022","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b5b9673723f6a882f45b837c2c40568171d4e72a","datavalue":{"value":"6248059","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870527$BF8DF913-5241-4744-94D9-4E01C623B2D7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bec68a7d1c96908f38ff9e6193e7592f52ba1668","datavalue":{"value":"rainbow subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870527$8B4ABF27-62C0-4B8C-995F-5A4D04A50C67","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"08e3e59396557736c1d3a627af68d9c3f9a06423","datavalue":{"value":"Gallai coloring","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870527$2CD16E05-9C08-416C-B3C8-7FC3487E9AE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"27f1059cc45ab0b30ab1419cefc906baa5da89b8","datavalue":{"value":"highly connected monochromatic subgraph","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870527$5DD96BE5-62F4-43F6-A003-2118B533B26B","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":"Q2870527$255B141A-1EE7-4B6A-AEBD-6CF0D84754F1","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"9e55b16dc292117613054073129b378a638dec66","datavalue":{"value":"https://doi.org/10.1137/120896906","type":"string"},"datatype":"url"},"type":"statement","id":"Q2870527$34174C5E-BCF2-4E4C-966B-7DE3B6C4537F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"0c66ebb267d4f4c53d8e3c30679e08e2379886a2","datavalue":{"value":"W2152158512","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q2870527$39E74D02-4831-406A-BBBB-3A6D60888757","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7362f455cf23d2d66071a0c7894dd03d803b7e31","datavalue":{"value":{"entity-type":"item","numeric-id":2401439,"id":"Q2401439"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1592685603ba1b1ab34731215917f681dd6a4aaa","datavalue":{"value":{"amount":"+0.8223883","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$1AF125A6-8D08-4DF9-BA07-E1183379DB91","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"41d4170a4f4a60c2047c4e8bf313e85147aa0300","datavalue":{"value":{"entity-type":"item","numeric-id":625377,"id":"Q625377"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"ed52d2b3c56969215f135daddab9989bc4494ba7","datavalue":{"value":{"amount":"+0.82237303","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$9C1C3778-F685-43E8-B5CC-2EFD88B1C3ED","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"d6fae56499f6ba029e65b2484905db88ee128a93","datavalue":{"value":{"entity-type":"item","numeric-id":905898,"id":"Q905898"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"2feb688c8174476c88a764773fce61f976ee3668","datavalue":{"value":{"amount":"+0.8156699","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$540D3D97-2B68-4A2B-A8B7-A88EF45D799A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ed5a2ccebee9149880996e9273da9aebcb4893fc","datavalue":{"value":{"entity-type":"item","numeric-id":2514967,"id":"Q2514967"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"444a0f7ec03d5e8f82c3b5a257480c9b7a2f7373","datavalue":{"value":{"amount":"+0.81520456","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$349D3B95-7EDD-4CD4-89A1-6E3D6E99F048","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"fe0eec2bc32ce58e964b139f568423bd58c00c6a","datavalue":{"value":{"entity-type":"item","numeric-id":2477397,"id":"Q2477397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"7687501d94a01bc51b2c0eacbf2b70c95ba79fde","datavalue":{"value":{"amount":"+0.8027908","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$3EA09C10-9114-4179-B1C6-2D5F1DA50274","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"ebd862de9ddda368b9c41e325f510299ebeb6270","datavalue":{"value":{"entity-type":"item","numeric-id":2045397,"id":"Q2045397"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b5805df6495769de0467a7e4b0d1f45f625f40bd","datavalue":{"value":{"amount":"+0.80099213","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$7962F43A-0A80-42A3-867D-6478B286D906","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"89b43d82d2736a4f6b023faf942fdab91fe7e728","datavalue":{"value":{"entity-type":"item","numeric-id":1015436,"id":"Q1015436"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"dac23f2adf4975034f9b3e1ba0af5e2edf7fcfd8","datavalue":{"value":{"amount":"+0.7911512","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$25DDAE3D-BDFD-4D81-9867-898F964BFDE4","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":"dd603748a4b9919d184fc86be88e467935b56e57","datavalue":{"value":{"amount":"+0.77559423","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$7C32DD85-8A83-41D1-9281-9D8897E2480C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"72cbe7639c3a0bc800885d9fe5fb45d82b455a1c","datavalue":{"value":{"entity-type":"item","numeric-id":6158362,"id":"Q6158362"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a61d95379bb8f2af98d0b0ff6ccaf6c9853fba90","datavalue":{"value":{"amount":"+0.7732879","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$32737D28-BD8A-4860-B480-2CA78D8B4BAD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"035942e6a0e55880a582d4d438d0f186b26cfb96","datavalue":{"value":{"entity-type":"item","numeric-id":2960949,"id":"Q2960949"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4e167ee3dd0cfb96a408621eb5f5619c64dc1f42","datavalue":{"value":{"amount":"+0.7729271","unit":"1"},"type":"quantity"},"datatype":"quantity"}],"P1660":[{"snaktype":"value","property":"P1660","hash":"ba354e87a58191d58d132c60481c945a3234ce85","datavalue":{"value":{"entity-type":"item","numeric-id":6534273,"id":"Q6534273"},"type":"wikibase-entityid"},"datatype":"wikibase-item"}]},"qualifiers-order":["P1659","P1660"],"id":"Q2870527$C097069E-A793-4F50-A797-26EB0F510E06","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"6bccbce207cee384937e04cb0e1ca96d1df8f80b","datavalue":{"value":{"text":"Forbidden rainbow subgraphs that force large highly connected monochromatic subgraphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q2870527$3FC75657-CD09-481A-95C5-4971CFB2D8FF","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"85355375c3720fb3ec21094e3a9c805068e78ac5","datavalue":{"value":"Let \\(k, r \\geq 2\\). We consider an edge-colored complete graph \\(K_n\\) on \\(n\\) vertices by \\(r\\) colors. A subgraph of \\(K_n\\) colored by \\(r\\) colors is almost spanning if it has \\(n - c\\) vertices where \\(c\\) is a constant independent of \\(n\\) and \\(r\\). \\textit{B. Bollob\u00e1s} and \\textit{A. Gy\u00e1rf\u00e1s} [Discrete Math. 308, No. 9, 1722--1725 (2008; Zbl 1137.05025)] conjectured that for \\(n > 4(k-1)\\), every 2-colored \\(K_n\\) contains a \\(k\\)-connected monochromatic subgraph on at least \\(n-2(k-1)\\) vertices. \\textit{L. Gerencser} and \\textit{A. Gyarfas} [Ann. Univ. Sci. Budap. Rolando E\u00f6tv\u00f6s, Sect. Math. 10, 167--170 (1967; Zbl 0163.45502)] studied the largest monochromatic subgraph in an \\(r\\)-colored \\(K_n\\). Since \\textit{H. Liu} et al. [J. Graph Theory 61, No. 1, 22--44 (2009; Zbl 1202.05079)] proved that the largest monochromatic \\(k\\)-connected subgraph in edge-colored complete graph \\(K_n\\) with \\(r\\) colors has approximately \\(\\frac{n}{r-1}\\) vertices, in order to guarantee monochromatic almost spanning \\(k\\)-connected subgraph, the authors of this paper proposed adding restrictions on the coloring. Let \\(G\\) be a graph. A coloring of the edges of \\(K_n\\) is rainbow \\(G\\)-free if it does not contain any copy of \\(F\\) whose edges have pairwise different colors. Let \\({\\mathcal G}\\) be the collection of graphs \\(G\\) satisfying the property that in every rainbow \\(G\\)-free coloring of \\(K_n\\) using \\(r\\) colors, there is a monochromatic almost spanning \\(k\\)-connected subgraph. Denote the path on \\(n\\) vertices by \\(P_n\\) and we obtain \\(P_4^+\\) from \\(P_4\\) by adding a vertex adjacent to an internal vertex of \\(P_4\\). The authors proved that the set \\({\\mathcal G}\\) consists of \\(K_3\\), \\(P_6\\), \\(P_4^+\\), and their connected subgraphs having at least three vertices.","type":"string"},"datatype":"string"},"type":"statement","id":"Q2870527$AE55A1CB-172C-402C-A042-183FD0499472","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"39a7d342c26e9c51a26b2dd58ca05e7a15147f88","datavalue":{"value":{"entity-type":"item","numeric-id":844221,"id":"Q844221"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q2870527$6FC3E637-0EB6-44B9-9EFC-33118C6BE12E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Publication:2870527","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Publication:2870527"}}}}}