{"entities":{"Q1671656":{"pageid":1682397,"ns":120,"title":"Item:Q1671656","lastrevid":68108409,"modified":"2026-04-12T21:29:31Z","type":"item","id":"Q1671656","labels":{"en":{"language":"en","value":"Vertex covering with monochromatic pieces of few colours"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6933715"}},"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":"Q1671656$EDC19B08-FE3C-4006-B998-9BC7E55CA691","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"c27da233b417a4e6e0acf4279c0776cf1c31b231","datavalue":{"value":{"text":"Vertex covering with monochromatic pieces of few colours","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1671656$50B00AF1-E990-4455-BA35-1C9464023055","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"ead22cdf9c820bac6e5ef69cdb9464e39923034c","datavalue":{"value":"1395.05091","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1671656$E4B4AE8A-FE37-4982-9659-C83EF7CEB6D0","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"5c4d94ea57f0a8b092ec8e07bb76431aaed6da68","datavalue":{"value":{"entity-type":"item","numeric-id":1671655,"id":"Q1671655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$FCE8929F-1458-4128-BB39-EDDFE8135031","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"fc4d66bfe8a3b8816a49b3ee57d66f387a2d633b","datavalue":{"value":{"entity-type":"item","numeric-id":350718,"id":"Q350718"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$A94754A8-AFAF-4AD6-8150-BDEE71B30B16","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":"Q1671656$356EC3E9-8C1F-4155-9E8D-8F3C2B456D3D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"9da71b137af9cfccb6c7b456e1c82e88aebc6157","datavalue":{"value":{"time":"+2018-09-07T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q1671656$B8AF4CDB-9C68-4562-895B-9BE752D65CA6","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"43d495bf669d4b761c5b7fc5020fc6f85a912b04","datavalue":{"value":"https://arxiv.org/abs/1711.01557","type":"string"},"datatype":"url"},"type":"statement","id":"Q1671656$ED65F653-5CA7-4BEF-8AA2-50720C612922","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd355a72ce90364eec791495c886a4ac7c6b00d8","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v25i3p33","type":"string"},"datatype":"url"},"type":"statement","id":"Q1671656$CDCF723F-0C6A-4EE9-B5C6-1780F1441B21","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"aabd04123b9e6cf0433de1e4b1c318f328341789","datavalue":{"value":"Summary: In [Math. Pannonica 6, No. 1, 7--10 (1995; Zbl 0828.05040)], \\textit{P. Erd\u0151s} and \\textit{A. Gy\u00e1rf\u00e1s} proved that in every \\(2\\)-colouring of the edges of \\(K_n\\), there is a vertex cover by \\(2\\sqrt{n}\\) monochromatic paths of the same colour, which is optimal up to a constant factor. The main goal of this paper is to study the natural multi-colour generalization of this problem: given two positive integers \\(r,s\\), what is the smallest number \\(pc_{r,s}(K_n)\\) such that in every colouring of the edges of \\(K_n\\) with \\(r\\) colours, there exists a vertex cover of \\(K_n\\) by \\(pc_{r,s}(K_n)\\) monochromatic paths using altogether at most \\(s\\) different colours?  For fixed integers \\(r > s\\) and as \\(n\\to\\infty\\), we prove that \\(pc_{r,s} (K_n) = \\Theta(n^{1/\\chi})\\), where \\(\\chi=\\max\\{1,2+2s-r\\}\\) is the chromatic number of the Kneser graph \\(\\mathcal{KG}(r,r-s)\\). More generally, if one replaces \\(K_n\\) by an arbitrary \\(n\\)-vertex graph with fixed independence number \\(\\alpha\\), then we have \\(pc_{r,s}(G) = O(n^{1/\\chi)}\\), where this time around \\(\\chi\\) is the chromatic number of the Kneser hypergraph \\(\\mathcal{KG}^{(\\alpha+1)}(r, r-s)\\). This result is tight in the sense that there exist graphs with independence number \\(\\alpha\\) for which \\(pc_{r,s}(G)=\\Omega(n^{1/\\chi})\\). This is in sharp contrast to the case \\(r=s\\), where it follows from a result of \\textit{G. N. S\u00e1rk\u0151zy} [J. Graph Theory 66, No. 1, 57--64 (2011; Zbl 1222.05075)] that \\(pc_{r,r}(G)\\) depends only on \\(r\\) and \\(\\alpha\\), but not on the number of vertices.  We obtain similar results for the situation where instead of using paths, one wants to cover a graph with bounded independence number by monochromatic cycles, or a complete graph by monochromatic \\(d\\)-regular graphs.","type":"string"},"datatype":"string"},"type":"statement","id":"Q1671656$8BFC0471-CB3D-4E4B-87F7-046272EE9E69","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1671656$426B4473-8173-4694-8C1D-D7DF7FBB1DAA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"8afe3c5a9fa0449dca60371c176beebeb6e1d999","datavalue":{"value":"05C55","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1671656$7FC64629-7895-49A7-A286-F41624D81764","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"a5781e7c47dcd8009e557096e2e96d38db585aa3","datavalue":{"value":"6933715","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1671656$34B4209D-48A3-4F2C-9E26-33B5D10FFB95","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"bdf4dc3db86d44e89a36d3ec12340c2571d04f06","datavalue":{"value":"graph theory","type":"string"},"datatype":"string"},"type":"statement","id":"Q1671656$4FD79D20-CD80-4DDC-81CF-81F999FDC214","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"60f2c70715198726483e37571aeac11f9584945f","datavalue":{"value":"monochromatic covering","type":"string"},"datatype":"string"},"type":"statement","id":"Q1671656$CA8C2066-170A-4836-A9CF-2BE2FA69F577","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":"Q1671656$9BB94145-D5E3-4484-9A96-0D5F6BA62FF7","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"fd90d5739eb00fa5a5ab0736d73a1e03fd1a98c1","datavalue":{"value":{"entity-type":"item","numeric-id":873644,"id":"Q873644"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$06D233E6-CEA4-4AF1-B821-8D89943A41B8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"98ce170d2c8dd176c8630d55b691b61a25e14b75","datavalue":{"value":{"entity-type":"item","numeric-id":3527536,"id":"Q3527536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$551748EE-4A21-410C-BE20-D1213B9273AD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"206a687e585ae4987de04449b0298662542d9a57","datavalue":{"value":{"entity-type":"item","numeric-id":3743337,"id":"Q3743337"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$1FC28BF0-556C-437B-860E-60A815A0EAB4","rank":"normal"},{"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":"Q1671656$071BB38A-3BAB-4E12-9187-AF8FA2DCC92E","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":"Q1671656$8EB7042D-F279-4199-98E4-B571761FCAFB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"498dcb5848e7c4e5670044691c30f77e6a2a1d8e","datavalue":{"value":{"entity-type":"item","numeric-id":965246,"id":"Q965246"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$CF0FC0A2-D9D9-45D8-8257-A9ECCF5DD8B4","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":"Q1671656$2C784766-9156-4570-87F6-452168A37AD1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"9aa53bcdbba9fc3beac07f68b85d42d1a3bb712d","datavalue":{"value":{"entity-type":"item","numeric-id":4841660,"id":"Q4841660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$F54B7602-5BC9-4E22-AC25-BA07BB04E2DD","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"460aee082e5f134898d78d77090e3cbd9bb12b19","datavalue":{"value":{"entity-type":"item","numeric-id":1174783,"id":"Q1174783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$A0907E53-54C2-46CB-A9B2-6BA84888098E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"17b653dd53d1337f97f95f06add9798835a41db8","datavalue":{"value":{"entity-type":"item","numeric-id":5548200,"id":"Q5548200"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$48793AB5-EF20-424C-8874-88C241113F65","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"1bb82b9295a2e5b662a9f610a631fc69b1aa838e","datavalue":{"value":{"entity-type":"item","numeric-id":501026,"id":"Q501026"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$C80712A7-704C-4E7A-A6CB-607FF2ED7629","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ce808c9c137a7e7af67324c70f8751049fce6c4a","datavalue":{"value":{"entity-type":"item","numeric-id":4749866,"id":"Q4749866"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$8D353B6A-EE6D-45A6-927B-EE1F703B0D9C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"2b0958f0fee48b60f0996400b57c1e5e51b18ad6","datavalue":{"value":{"entity-type":"item","numeric-id":3977492,"id":"Q3977492"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$985E9D9E-DEAA-4DDB-90CC-7CF267AC4428","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"76c111e8bb2e4c78a301c549458e60750fc69d64","datavalue":{"value":{"entity-type":"item","numeric-id":279224,"id":"Q279224"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$B5802CDE-63F2-4319-867B-CF4A92EE98E6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"f91b2584b67b9545af0692dcfcce7ea30265109e","datavalue":{"value":{"entity-type":"item","numeric-id":859613,"id":"Q859613"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$EF566972-D2CF-452A-8F80-FAA3AA041FA3","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e5a8ab9bfec7717015a64ba42749394bddd92356","datavalue":{"value":{"entity-type":"item","numeric-id":1354726,"id":"Q1354726"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$317D6672-EAB3-466E-BC88-A476E4E5C414","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5ed0b82ae82773b964a96367bdde8d8d4e478307","datavalue":{"value":{"entity-type":"item","numeric-id":4878666,"id":"Q4878666"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$A733AEAE-8852-4E88-A064-C4BF03EB674B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c428f1852e95384416608cd782a84ad75e86d42b","datavalue":{"value":{"entity-type":"item","numeric-id":755592,"id":"Q755592"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$9E24C2EB-0566-492D-8A5D-E39F104B8715","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5c3dd5b7839575f7266f87612cda795c76e65838","datavalue":{"value":{"entity-type":"item","numeric-id":4238172,"id":"Q4238172"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$5E988D48-51B4-4399-980E-46A54DBEB3B2","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"e86cf0bc297fe73fd3ab8c0acdc104ed6457c3f8","datavalue":{"value":{"entity-type":"item","numeric-id":402591,"id":"Q402591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$1F316BCB-E7A2-4BFB-9CFC-672E0D448B5B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a87cbbd9529f38ff9ec15c618e270c6f3aed3bab","datavalue":{"value":{"entity-type":"item","numeric-id":4920655,"id":"Q4920655"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1671656$22A18693-557E-4F8C-BD6E-A7F3557FD890","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":"Q1671656$77AE031A-8718-453C-9AAB-643E05D5AF52","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"3bdea4daefe2d5056bb1dc468e55acb42990c940","datavalue":{"value":"bafkreifj5lu4o4feq55ucdmbrfka3mias7coakkml5tkgzyngj4xhhjk54","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1671656$D83DBC45-C66E-46E7-A0FE-3F45F5C0D6B3","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"01c409903e6ab86bbc4660a2b71f6dc1b7e960b9","datavalue":{"value":{"entity-type":"item","numeric-id":1174783,"id":"Q1174783"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82e6c429c3146db52bfcfd34890089befa49d3b8","datavalue":{"value":{"amount":"+0.8629336357116699","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":"Q1671656$61C8C1D4-F4C6-4CC5-9A13-F852B7210CCC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"a9894397526ff8dd1ac92c2d7b523f0c4591051e","datavalue":{"value":{"entity-type":"item","numeric-id":4625023,"id":"Q4625023"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"82e6c429c3146db52bfcfd34890089befa49d3b8","datavalue":{"value":{"amount":"+0.8629336357116699","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":"Q1671656$C5616508-A125-4463-BD13-DBAD0F62E464","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"048dc22ede40a7862177aff4737cb941b107bc5d","datavalue":{"value":{"entity-type":"item","numeric-id":4841660,"id":"Q4841660"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48f07bcd724377f572736adb1f32773fb9bc898b","datavalue":{"value":{"amount":"+0.8510543704032898","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":"Q1671656$710BF57E-4AC5-49B7-8D11-D59AB27B9C76","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"162d8842a75fb6a578b2d6a3b95c17378cf1c407","datavalue":{"value":{"entity-type":"item","numeric-id":402591,"id":"Q402591"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"48f07bcd724377f572736adb1f32773fb9bc898b","datavalue":{"value":{"amount":"+0.8510543704032898","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":"Q1671656$4763E5C0-6B83-4F89-A8BA-B721852600FF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"846fce68af2814dfe435848c24f0ef23c9548f57","datavalue":{"value":{"entity-type":"item","numeric-id":3483311,"id":"Q3483311"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4f99a9c9fecda3c59e2be90eabff5b8e35d494fd","datavalue":{"value":{"amount":"+0.8435211181640625","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":"Q1671656$2FCE8A98-CCEF-40A2-89B2-E0508E39503C","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Vertex covering with monochromatic pieces of few colours","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Vertex_covering_with_monochromatic_pieces_of_few_colours"}}}}}