{"entities":{"Q878646":{"pageid":880494,"ns":120,"title":"Item:Q878646","lastrevid":65037864,"modified":"2026-04-11T23:54:03Z","type":"item","id":"Q878646","labels":{"en":{"language":"en","value":"Independence number and vertex-disjoint cycles"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 5146849"}},"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":"Q878646$DB481053-3E44-463C-8B71-87A2CE286D89","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"42a9e1766039b7d2d6eb3d95b445482e8269e9c7","datavalue":{"value":{"text":"Independence number and vertex-disjoint cycles","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q878646$443D4BB6-AF4D-4119-A289-7451B8B63855","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"8be480dd06852ab98ff73629c344a7956f741768","datavalue":{"value":"1117.05080","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q878646$54678F4C-8B63-497A-9935-7E8D569362AA","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"a670df13e76d03f298849c21819158785379e5e5","datavalue":{"value":{"entity-type":"item","numeric-id":234310,"id":"Q234310"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$3BC40BF2-84BB-4E8E-B214-410BFD98A2E1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"bfa215cf6b30ee4d0ec9785cb7e068b69f1b3a72","datavalue":{"value":{"entity-type":"item","numeric-id":186104,"id":"Q186104"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$A8DA575C-86B0-408B-8775-48C0034EF73F","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a57de2e11ea0a7c1b4e027ef0d1354f56003f3b7","datavalue":{"value":{"entity-type":"item","numeric-id":214980,"id":"Q214980"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$FF129743-34D7-479B-A62A-7ECB1BB3D109","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"6b09124aade2f9a2d1dad9d1d88ddbbb2bdabd00","datavalue":{"value":{"entity-type":"item","numeric-id":228794,"id":"Q228794"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$83CFE86F-AEE7-4B20-ADB2-B8D515DAB1A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"5aedeb5c029a3e220345fbf20050e7d4231517fc","datavalue":{"value":{"entity-type":"item","numeric-id":582576,"id":"Q582576"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$846ABA42-FE63-48D8-85F7-B756D5972F72","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"38665fe4ed2b835132254a58832c329597060029","datavalue":{"value":{"entity-type":"item","numeric-id":175483,"id":"Q175483"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$E53EAC3A-B3BC-4E44-BF4B-0ECB664A365B","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"018eb3d5a1529ba4d911dfe810dafc033402deeb","datavalue":{"value":{"time":"+2007-04-26T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q878646$BFDE394F-16CC-46FC-AC01-B5B9E1627865","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"82369be05d760373b1bbda5138f2cafffed73528","datavalue":{"value":"For given integers \\(k\\) and \\(\\alpha\\), let \\(f(k, \\alpha)\\) be the maximum order of a (finite simple) graph \\(G\\) with independence number \\(\\alpha (G) \\leq \\alpha\\), which has no \\(k\\) vertex-disjoint cycles. The authors present constructive sharp lower bounds for \\(f(k, \\alpha)\\) and derive upper bounds using Ramsey numbers. It is shown that \\(f(k, \\alpha ) \\geq 3k+2\\alpha -3\\) and that equality holds for \\(\\alpha\\) between 1 and 5, or \\(k\\) between 1 and 2. Moreover, the existence of constants \\(c_{\\alpha}\\) (depending only on \\(\\alpha\\)) and \\(t_k\\) (depending only on \\(k\\)) such that \\(f(k, \\alpha)\\) is bounded from above by \\(3k+c_{\\alpha}\\), or \\(2\\alpha +t_k\\) respectively, is established, but it is shown there exists no absolute constant \\(c\\) such that \\(f(k, \\alpha) \\leq c(k+\\alpha )\\). The finding of an explicit pair of integers \\(k\\) and \\(\\alpha \\) such that \\(f(k, \\alpha) > 3k +2\\alpha - 3\\) is left as a challenging open problem.","type":"string"},"datatype":"string"},"type":"statement","id":"Q878646$0AF7A495-D536-411A-981B-F1B597741996","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"489b50af879f20c258267402ff7bb6342fefbc88","datavalue":{"value":{"entity-type":"item","numeric-id":588147,"id":"Q588147"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$B0DAC801-805B-4BB0-B193-CD30CA8CF295","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"cb1e2924ba238bc47b6e89cc71d65b0484b3d905","datavalue":{"value":"05C69","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q878646$BE85AF58-4244-4860-849E-80309C6CBC60","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"f3a5e47548ef139717b317f83801cfef606a623d","datavalue":{"value":"05C38","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q878646$8FC09E20-D49D-4D1C-8807-69C3F071B4AF","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"b40e6ad95abb64ed6cb0917d5687ff8f3be33ac8","datavalue":{"value":"5146849","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q878646$A7A104ED-65F7-454A-AD18-D5421922D483","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":"Q878646$77465B0D-62CA-4B78-A786-453B4F6E72CD","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"560f2bea1797bc7a6993f490f81cf9ec4862ecc5","datavalue":{"value":"https://doi.org/10.1016/j.disc.2005.11.086","type":"string"},"datatype":"url"},"type":"statement","id":"Q878646$28B1069F-EE6F-4FFD-90AA-3E8A798AB945","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"2f73c3a1834fd86ec2a92755e49ead84f5a51ec0","datavalue":{"value":"W2052169294","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q878646$BD9F7E00-6038-4FE3-9FC8-9917AF10B2D2","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"559dbe579a3334aacf82df2fdcef598c181017c4","datavalue":{"value":{"entity-type":"item","numeric-id":5422499,"id":"Q5422499"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$1641DCA7-1D9A-4D45-B234-7B944105F968","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5955caa91359ba578c004a79981e6b39abcfdaa2","datavalue":{"value":{"entity-type":"item","numeric-id":5728985,"id":"Q5728985"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$FA044E9E-3BEB-49AE-BF52-44990CE6EA92","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"36d830e5daa965f09732ab7bbed944f6ad41e6f1","datavalue":{"value":{"entity-type":"item","numeric-id":1924121,"id":"Q1924121"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$54F985E6-7E10-4A12-AC73-6B5EB9AE50BF","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b45322291683fba90e71ffd780e76ef4254ee4f5","datavalue":{"value":{"entity-type":"item","numeric-id":1307442,"id":"Q1307442"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$33289789-5EC0-4D03-B4CD-6DB71453BA04","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"27b91fb34b309a1448e42736f924e3a5012ab649","datavalue":{"value":{"entity-type":"item","numeric-id":3253064,"id":"Q3253064"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$6F163439-8036-4F71-8DF2-A8F5A1E2F4E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"38e45149a7172ef8e70d14a58b7ed8cc038c453c","datavalue":{"value":{"entity-type":"item","numeric-id":1301840,"id":"Q1301840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q878646$78422DFE-BE1E-4D42-B61B-3A215B69E214","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"7797d02a2da33fc9e2da30ee007fb1deb4efade9","datavalue":{"value":"10.1016/J.DISC.2005.11.086","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q878646$D55BCF99-4846-4C7D-9BFB-E333212E1F64","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"851c0b723761568a5ecd3f9eb085c9b68403de23","datavalue":{"value":{"entity-type":"item","numeric-id":2166216,"id":"Q2166216"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"4bc6bbbb6a8aafb046fa91d89edb70aadc22dd5f","datavalue":{"value":{"amount":"+0.8124480247497559","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":"Q878646$1FD4600C-BE80-464E-B0C4-4BB54668CE68","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c083715b19c41a66e8cb61e8b1e6d45f965d64bb","datavalue":{"value":{"entity-type":"item","numeric-id":554004,"id":"Q554004"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"e1e9e24828ff7483864b32eff48faeaa16d5c160","datavalue":{"value":{"amount":"+0.8115103244781494","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":"Q878646$1F86F29E-7198-45BC-AD2A-D669B391C6F4","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7789942460f57d90e4dbcdd8b8267e59549cbc74","datavalue":{"value":{"entity-type":"item","numeric-id":1768585,"id":"Q1768585"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"964af7df13d51a6a76188d3691293bd28161f4a7","datavalue":{"value":{"amount":"+0.8040573000907898","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":"Q878646$141D37F4-3925-4452-8D34-29EFDA8C5263","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7e097e1a7d9ea437752cf7a784884d09ddfb8f6a","datavalue":{"value":{"entity-type":"item","numeric-id":3220625,"id":"Q3220625"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"53659e50bf4bad61caf3972ea9f5378d649454a3","datavalue":{"value":{"amount":"+0.7902507185935974","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":"Q878646$27D84624-769F-4AFA-977F-DD08FC99F98B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6d28bee22444607df2d48babd2ac346a91e9d670","datavalue":{"value":{"entity-type":"item","numeric-id":1301840,"id":"Q1301840"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9f6aac693811225d4bb16a186a49dd0b862a6e96","datavalue":{"value":{"amount":"+0.7698782682418823","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":"Q878646$9300C4E3-6BB0-4321-B50F-7C93A76DEA88","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Independence number and vertex-disjoint cycles","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Independence_number_and_vertex-disjoint_cycles"}}}}}