{"entities":{"Q1893949":{"pageid":1904691,"ns":120,"title":"Item:Q1893949","lastrevid":71090514,"modified":"2026-04-13T19:25:10Z","type":"item","id":"Q1893949","labels":{"en":{"language":"en","value":"On the ultimate independence ratio of a graph"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 773829"}},"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":"Q1893949$71B49E09-60AA-4EFB-BC73-5CE92DCB328C","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"b4bb5485ccf8860fc574f776104443618253ee0e","datavalue":{"value":{"text":"On the ultimate independence ratio of a graph","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q1893949$18A8C7BE-D272-4998-AE54-025C0A1B6E6C","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"7ed75d0c210ae6600fe1df5c36928a5be4386cb1","datavalue":{"value":"0829.05026","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893949$3C418E4C-7623-47CD-8339-E2730104688A","rank":"normal"}],"P27":[{"mainsnak":{"snaktype":"value","property":"P27","hash":"8466b84c6f1eb0b93d499214b3008228f774dc00","datavalue":{"value":"10.1016/0195-6698(95)90030-6","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893949$FC2A558E-CAA3-40BD-95FC-8D2616A7A2A3","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"13f926ec1013785b3e69b5c6d964392731ed9766","datavalue":{"value":{"entity-type":"item","numeric-id":221686,"id":"Q221686"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$41FFAB7C-FBDF-4095-884A-76E61145FB88","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"697be813fbdf5940bf37c14fbe59ac96ce0fdc57","datavalue":{"value":{"entity-type":"item","numeric-id":685306,"id":"Q685306"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$24784C82-91AD-459B-AE4A-DBFEDD3F5AE9","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"a3b5375d01a59455d415f2afee9796bf93e2b3c4","datavalue":{"value":{"entity-type":"item","numeric-id":338573,"id":"Q338573"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$583BB488-0397-4761-9B60-DDB2B56CF7A1","rank":"normal"}],"P200":[{"mainsnak":{"snaktype":"value","property":"P200","hash":"b113bc4ac7ed430093230b872c083cde59919509","datavalue":{"value":{"entity-type":"item","numeric-id":166287,"id":"Q166287"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$09981334-64C4-4582-B6FC-CE6769D7D09D","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"543311796a706d9993a23b2a3c8fd06a2885b7c0","datavalue":{"value":{"time":"+1996-01-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":"Q1893949$C19B4815-9887-423F-ACE1-D5B610B68DD6","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e30f5c03cb67b9e1e99ed1d922eed25d96615175","datavalue":{"value":"The ultimate independence ratio \\(I(G)\\) of a graph \\(G\\) is the limit, as \\(k \\to \\infty\\), of the sequence of independence ratios of the (box) powers \\(G^k\\). It is shown that \\(I(H)\\leq I(G)\\) whenever there is a graph homomorphism from \\(G\\) to \\(H\\). Using this monotony property, it is proved that \\(1/ \\chi (G) \\leq I(G) \\leq 1/\\chi_f (G)\\) where \\(\\chi(G)\\) and \\(\\chi_f (G)\\) are the chromatic and the fractional chromatic number of \\(G\\). This result yields a number of consequences; in particular, exact values of \\(I(G)\\) are computed for several classes of graphs (e.g., \\(I(G) = 1/2\\) if \\(G\\) is bipartite).","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893949$20A24A65-0408-43ED-9C55-B696F3F1E0AA","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"6f15d46cb8d4ffe0dbd9357e013b784d0f700114","datavalue":{"value":"05C15","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893949$96C755FE-0801-468F-86AD-6721B2309659","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"5a3bb76dbd41580d9287ece5137de80ddf22202f","datavalue":{"value":"05C35","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893949$827F068C-E491-4FB3-9C3D-D793C78FDA2C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"74e7832a915a62c417a3bf8c026eff5989fd94d3","datavalue":{"value":"05C25","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893949$8ECEB571-8F44-42B6-93C8-E600B9CA5D4A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"6b0e45a8d773c8192edfc86efc400c3465225eb0","datavalue":{"value":"773829","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893949$16E22647-30A2-407E-A45C-7AEB65020413","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"b89aa1b9eed71217ebf6a719487a219071558409","datavalue":{"value":"independence number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893949$BA91EE32-4342-4DBC-B85D-9594C20ADB27","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"9959f4529f084c9f1a7ebc0e808ee60a0113928f","datavalue":{"value":"chromatic number","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893949$1162CA66-67F3-4D54-8C38-B1AA82625089","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"41d36008e6107194b6e80d2da12a740a039c38f6","datavalue":{"value":"ultimate independence ratio","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893949$612D5D4F-BF34-4254-B495-B155472B67EC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"58712acbde860c0153062a2693545d5f45b74754","datavalue":{"value":"graph homomorphism","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893949$B715A504-9EB2-4B77-BCB5-6D282F9507AB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"450f536e7fb552c6ccec3a56f94165758881dbaf","datavalue":{"value":"fractional chromatic numbers","type":"string"},"datatype":"string"},"type":"statement","id":"Q1893949$78EE3335-10C2-4066-A116-3941AD316959","rank":"normal"}],"P1447":[{"mainsnak":{"snaktype":"value","property":"P1447","hash":"90c78b3265eaf03d2c9093f31b0f9730424156f8","datavalue":{"value":{"entity-type":"item","numeric-id":175610,"id":"Q175610"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$4F40D12F-C169-4C9D-B19F-4F74F0C561CD","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":"Q1893949$3E7E8480-915D-4BE0-99FC-F44263A5E387","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bbb9fd70d95785f6f8c41cd41e69c814bd61b9d9","datavalue":{"value":"https://doi.org/10.1016/0195-6698(95)90030-6","type":"string"},"datatype":"url"},"type":"statement","id":"Q1893949$193172FA-DACF-4B6D-AE09-95D3979F389F","rank":"normal"}],"P388":[{"mainsnak":{"snaktype":"value","property":"P388","hash":"504974d60c42c53e4a662412866072bda3d9f1c0","datavalue":{"value":"W1979898269","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q1893949$D37F5BEB-DAAB-4F81-BB9E-7CBF00F59A42","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"903439f2e74cb2c4e8e642d9bd06524c245b0bdb","datavalue":{"value":{"entity-type":"item","numeric-id":1246543,"id":"Q1246543"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$918B35BC-3E8A-4D01-88B0-3D9B83E6535D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"028def9dd9edd0eb8fa13d844ab0b826750be73a","datavalue":{"value":{"entity-type":"item","numeric-id":1062066,"id":"Q1062066"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$447BE153-9D11-43C5-8974-BDFFE54EEF87","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"70bd6502ec36ca8bf9e077b123e1ae22aab49a37","datavalue":{"value":{"entity-type":"item","numeric-id":4848762,"id":"Q4848762"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$FCA80F5C-1CDF-4597-B3E5-420C640EA2A0","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"6992a0f0c9c6dd16c2c6d91d9c5dedf2c9b3790f","datavalue":{"value":{"entity-type":"item","numeric-id":3966167,"id":"Q3966167"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$BA36ACA6-47B0-4270-B71C-920C75CC3C61","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"7f35321e17b622ce5311296b9b53a5fda06cc3b7","datavalue":{"value":{"entity-type":"item","numeric-id":1322230,"id":"Q1322230"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$87F04FF3-95CE-486B-8B04-30ED3E1CBBB6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"087e4ba6a98631ea6fc26923ddc853a6c69982f7","datavalue":{"value":{"entity-type":"item","numeric-id":4206781,"id":"Q4206781"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$0BFDA59C-943B-4394-B1DD-62216D636B7C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"8a48c289367846d2e6cbf6ff475cf182266d6c35","datavalue":{"value":{"entity-type":"item","numeric-id":4178914,"id":"Q4178914"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$3F63A54A-31D1-49D1-9580-C5E1E877ECF8","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"beebddf937b5d723f8911daf0b45941cb0d5d03d","datavalue":{"value":{"entity-type":"item","numeric-id":5525913,"id":"Q5525913"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$EA98B29D-C730-4657-BF29-549219C741DC","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ae4006c5e1748ff9864a8581d12faae23c03eb03","datavalue":{"value":{"entity-type":"item","numeric-id":810524,"id":"Q810524"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$B7D63187-F778-42EE-9526-D6CBDABEFDE7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"cc912dcc651afb9149194373546a803481a97d62","datavalue":{"value":{"entity-type":"item","numeric-id":1923515,"id":"Q1923515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q1893949$96F70E06-8994-484B-8529-191C9C87E231","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"6a8d6c1aa1fe461fe7d84df1def9a430089d39d6","datavalue":{"value":{"entity-type":"item","numeric-id":1923515,"id":"Q1923515"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"9c07b4bfca5b42d252bcfae01ef935cbd5c44b88","datavalue":{"value":{"amount":"+0.911017656326294","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":"Q1893949$4028223C-58F2-487B-8384-2D304C147C99","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"8e5b88b4d1086683c62397ba540921841b65f7f0","datavalue":{"value":{"entity-type":"item","numeric-id":635856,"id":"Q635856"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f07b737a3cb28af30986465efa72a61045d10850","datavalue":{"value":{"amount":"+0.9058055877685548","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":"Q1893949$48C4CDAB-0FF6-48E1-92FF-D1A57A2335F1","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7b8c289b90a337a5aebc15100cb7874515912ae7","datavalue":{"value":{"entity-type":"item","numeric-id":740645,"id":"Q740645"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"f423f28beefcdeffbf84570ebdabb04a56ddb3e5","datavalue":{"value":{"amount":"+0.8678794503211975","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":"Q1893949$FD2A9255-983F-489D-8E69-ED513A594D9B","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"7a8521f104f22174c644fe6b86a000e4ac4dffad","datavalue":{"value":{"entity-type":"item","numeric-id":3058536,"id":"Q3058536"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"1c989a79db1d1c70687563d1d6ffbc896761d487","datavalue":{"value":{"amount":"+0.8404331207275391","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":"Q1893949$0B9FAEA0-547E-47F4-BF06-2058831E3334","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"0f0d7275380e89321d9e6af8c88dc3fa5846a565","datavalue":{"value":{"entity-type":"item","numeric-id":4881293,"id":"Q4881293"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"02d86db89eb5715732372f020546fd68d8644327","datavalue":{"value":{"amount":"+0.8394941091537476","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":"Q1893949$92ED896B-48B6-4914-A8BB-FA359B8998BF","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"On the ultimate independence ratio of a graph","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/On_the_ultimate_independence_ratio_of_a_graph"}}}}}