{"entities":{"Q278884":{"pageid":280651,"ns":120,"title":"Item:Q278884","lastrevid":60604647,"modified":"2026-04-10T18:00:31Z","type":"item","id":"Q278884","labels":{"en":{"language":"en","value":"Guessing games on triangle-free graphs"}},"descriptions":{"en":{"language":"en","value":"scientific article; zbMATH DE number 6576594"}},"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":"Q278884$52DB073E-3F9C-484D-91D0-250D4B111C18","rank":"normal"}],"P159":[{"mainsnak":{"snaktype":"value","property":"P159","hash":"a9766ab658caca1059503ba9f7c040858b750909","datavalue":{"value":{"text":"Guessing games on triangle-free graphs","language":"en"},"type":"monolingualtext"},"datatype":"monolingualtext"},"type":"statement","id":"Q278884$0A8E6EA0-4A4B-4E43-B556-BA008657975B","rank":"normal"}],"P225":[{"mainsnak":{"snaktype":"value","property":"P225","hash":"33adb0ce562e9e8e57df69af3777c4eb70f393fa","datavalue":{"value":"1335.05119","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q278884$60917AF8-D3A0-47EA-8E9E-E2A2D3055A95","rank":"normal"}],"P16":[{"mainsnak":{"snaktype":"value","property":"P16","hash":"6bc2521eae45715fb417b046daabcb23d4401f14","datavalue":{"value":{"entity-type":"item","numeric-id":241258,"id":"Q241258"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$18EF878D-D7AF-4293-8F60-019ACD199E6D","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"2901901e4aa013f77c58b08037e10a8047141d05","datavalue":{"value":{"entity-type":"item","numeric-id":278883,"id":"Q278883"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$A2CBBC79-3C50-48D5-80FD-03216358D6E5","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P16","hash":"b988aafc908ad0705db140a886cbabb24b606a94","datavalue":{"value":{"entity-type":"item","numeric-id":195146,"id":"Q195146"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$2F8F8BD4-45C4-404A-8F03-288C19361DEA","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":"Q278884$8CEBF8C0-00BD-4A74-A130-5DE6B753256A","rank":"normal"}],"P28":[{"mainsnak":{"snaktype":"value","property":"P28","hash":"e14340917da0b560f1aa784255616bd78a4a4ba6","datavalue":{"value":{"time":"+2016-05-03T00:00:00Z","timezone":0,"before":0,"after":0,"precision":11,"calendarmodel":"http://www.wikidata.org/entity/Q1985727"},"type":"time"},"datatype":"time"},"type":"statement","id":"Q278884$2A5F0DDC-92B4-4397-8D04-4CDC165D9F30","rank":"normal"}],"P205":[{"mainsnak":{"snaktype":"value","property":"P205","hash":"bd71d93cdc294637b434711877be9cee3038dd27","datavalue":{"value":"https://arxiv.org/abs/1410.2405","type":"string"},"datatype":"url"},"type":"statement","id":"Q278884$D14DAB3F-EE6D-42B6-98CC-D19DEDC161CA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P205","hash":"fdb7341ae919ce4805863d16cf4450f4d433446c","datavalue":{"value":"http://www.combinatorics.org/ojs/index.php/eljc/article/view/v23i1p48","type":"string"},"datatype":"url"},"type":"statement","id":"Q278884$89010DEF-2837-4769-8705-53CB4F4C084A","rank":"normal"}],"P1448":[{"mainsnak":{"snaktype":"value","property":"P1448","hash":"e73ccf7fab67c9e6e53a666964d69bef25c43983","datavalue":{"value":"Summary: The guessing game introduced by \\textit{S. Riis} [Electron. J. Comb. 14, No. 1, Research paper R44, 17 p. (2007; Zbl 1122.05041)] is a variant of the ``guessing your own hats'' game and can be played on any simple directed graph \\(G\\) on \\(n\\) vertices. For each digraph \\(G\\), it is proved that there exists a unique guessing number \\(\\mathrm{gn}(G)\\) associated to the guessing game played on \\(G\\). When we consider the directed edge to be bidirected, in other words, the graph \\(G\\) is undirected, \\textit{D. Christofides} and \\textit{K. Markstr\u00f6m} [ibid. 18, No. 1, Research Paper P192, 19 p. (2011; Zbl 1337.05077)] introduced a method to bound the value of the guessing number from below using the fractional clique cover number \\(\\kappa_f(G)\\). In particular they showed \\(\\mathrm{gn}(G) \\geqslant |V(G)| - \\kappa_f(G)\\). Moreover, it is pointed out that equality holds in this bound if the underlying undirected graph \\(G\\) falls into one of the following categories: perfect graphs, cycle graphs or their complement. In this paper, we show that there are triangle-free graphs that have guessing numbers which do not meet the fractional clique cover bound. In particular, the famous triangle-free Higman-Sims graph has guessing number at least 77 and at most 78, while the bound given by fractional clique cover is 50.","type":"string"},"datatype":"string"},"type":"statement","id":"Q278884$829D970B-A0D5-4444-8B98-BFE3F6B8363F","rank":"normal"}],"P226":[{"mainsnak":{"snaktype":"value","property":"P226","hash":"1be7cda1f2fda1d13448035bf1c8e3fcef0c4ff8","datavalue":{"value":"05C57","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q278884$849F7900-E574-49C6-B3FA-06CFCB1EDEEB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P226","hash":"51140ae2bebd38d405ad1731d3b61ebf4b26c4ac","datavalue":{"value":"91A43","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q278884$57727B81-91BF-4FDE-A2A0-D534122FD21A","rank":"normal"}],"P1451":[{"mainsnak":{"snaktype":"value","property":"P1451","hash":"696a9bbc795d0673eea6f7d229312461fe53581a","datavalue":{"value":"6576594","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q278884$DBB4EE5E-02D0-4AEC-8C28-8F68278705B7","rank":"normal"}],"P1450":[{"mainsnak":{"snaktype":"value","property":"P1450","hash":"d4e50ffc0b0d235b7a99e9234aa5081507c4b1cc","datavalue":{"value":"guessing game","type":"string"},"datatype":"string"},"type":"statement","id":"Q278884$8764E519-686A-4845-BC61-FE028F795F56","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"2e77c91606cbe94d171bddd8a376dc4793708199","datavalue":{"value":"fractional clique cover","type":"string"},"datatype":"string"},"type":"statement","id":"Q278884$A60B7AF4-20B0-4DA9-9EE8-224452E72C93","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1450","hash":"938507bc54d83812726579a12a77d5cd2af4ae8b","datavalue":{"value":"triangle-free graphs","type":"string"},"datatype":"string"},"type":"statement","id":"Q278884$F54D57EE-AE8D-42B4-AAEA-12FE14D1D54D","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":"Q278884$E7949D61-5D41-4DB4-ACAA-F15CAB803450","rank":"normal"}],"P223":[{"mainsnak":{"snaktype":"value","property":"P223","hash":"bb0ac2e249fa1445ed2b545a6ca0aef4baaf2417","datavalue":{"value":{"entity-type":"item","numeric-id":685993,"id":"Q685993"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$E9C3C251-1466-4E50-9884-3FBFC3DF3C5A","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"a70b1ed67593050d2f1fbb22fe7e43163b23ffd3","datavalue":{"value":{"entity-type":"item","numeric-id":4501758,"id":"Q4501758"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$D57D879E-48AA-4B46-A045-668290823BE6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"72fe0ec44efa8fde458e9b5c8560356ff77ddb2b","datavalue":{"value":{"entity-type":"item","numeric-id":5358568,"id":"Q5358568"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$751313AD-EE4D-40A6-8B0C-67CD0D200252","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"b23e7bc5a087cd8dcbc80276e5103647248fb256","datavalue":{"value":{"entity-type":"item","numeric-id":4000288,"id":"Q4000288"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$479B8AB9-42B6-42C4-AA2F-38A8BE95636E","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"af9db6d262ff1398c9aaaf06b165d16d53838ffe","datavalue":{"value":{"entity-type":"item","numeric-id":640453,"id":"Q640453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$3180026C-7165-4449-93DA-5AC52D47BABB","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"763e3905bf47dfe4b400832ecce38198b0d97320","datavalue":{"value":{"entity-type":"item","numeric-id":5490912,"id":"Q5490912"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$F70DA0E4-33D3-4B21-92C6-82F8238D3DA7","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"68b228bccaefad444c30e923880336a303326f74","datavalue":{"value":{"entity-type":"item","numeric-id":3548143,"id":"Q3548143"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$F0C41449-B0A6-4F8B-846C-597BFDD88797","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"5fb5afb97ea0d8112ed4c35661851a62c69dd4a3","datavalue":{"value":{"entity-type":"item","numeric-id":5272296,"id":"Q5272296"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$87AC063A-4D0B-4FA5-A4C4-D89D51034B46","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"ef0c96e565e961f2dc1f307683031583d69731f5","datavalue":{"value":{"entity-type":"item","numeric-id":2536637,"id":"Q2536637"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$9343998C-FA14-4B6A-962F-5F5535924A34","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"501aefe4754342fb8d5444baacca037714207964","datavalue":{"value":{"entity-type":"item","numeric-id":4999425,"id":"Q4999425"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$C41F1DB9-17A7-4EEE-BAB2-CD604264F8B6","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"508e381da34632e8ddcbb5084ac9d5fc2143938e","datavalue":{"value":{"entity-type":"item","numeric-id":2918398,"id":"Q2918398"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$A254C0DE-1923-4E1D-83C0-8385901C5993","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"bc6e42bbd28ad0df988766a128f5b2916ee17be6","datavalue":{"value":{"entity-type":"item","numeric-id":2372888,"id":"Q2372888"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$32783C00-2E33-4D73-9CC2-6E77EB8EF521","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"c11c80f0e3b81add992df12726dcf213d85ff90e","datavalue":{"value":{"entity-type":"item","numeric-id":3548899,"id":"Q3548899"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$B076F0CD-352D-4996-BF06-DC0C0F8D9A86","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"01e1523547ed5080954974f38a6cf2bcd622cbb3","datavalue":{"value":{"entity-type":"item","numeric-id":4036702,"id":"Q4036702"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$A0E913A5-ED60-40AF-BE89-4AC3CB7D2366","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P223","hash":"aecc9a1dd2df2d0ffa7d5fff52179fd21322755c","datavalue":{"value":{"entity-type":"item","numeric-id":4701115,"id":"Q4701115"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","id":"Q278884$0BF30623-C455-4E33-A7BA-C0AED1CE3703","rank":"normal"}],"P1633":[{"mainsnak":{"snaktype":"value","property":"P1633","hash":"2809d939a743962e566917555799bd6e011f7707","datavalue":{"value":"bafkreiemphwj3shetuk6b7chw2gucgmmh3y5n2zasu5erc67t4x22zdtte","type":"string"},"datatype":"external-id"},"type":"statement","id":"Q278884$5691D65E-83E3-462D-B4D8-14E51FEB4F5D","rank":"normal"}],"P1643":[{"mainsnak":{"snaktype":"value","property":"P1643","hash":"f417cb0b0c290c0365423fe2fcdc118ee139d5ac","datavalue":{"value":{"entity-type":"item","numeric-id":640453,"id":"Q640453"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"b3be03c3ccf7bf5db509f94c2c6d80adf213f6fc","datavalue":{"value":{"amount":"+0.8417893052101135","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":"Q278884$20493C6D-00FA-4607-AB23-7A04E4B1C8DA","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"c4b7f254632cb6d4a1d6f1af71b3717ce08b1138","datavalue":{"value":{"entity-type":"item","numeric-id":777481,"id":"Q777481"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"a07170319a0961c76c5d9354ec9d439a5e3e7d55","datavalue":{"value":{"amount":"+0.8055656552314758","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":"Q278884$6B40EA56-FCF1-4043-8430-690CAEBCCD5C","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"9906d3f0f1098d65420b89b968b30d5dea79f92c","datavalue":{"value":{"entity-type":"item","numeric-id":2152800,"id":"Q2152800"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"bd7e1adbf7f9ef9beb628b4cb8675bddf3539545","datavalue":{"value":{"amount":"+0.7994649410247803","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":"Q278884$B6DE6FC1-BE82-429E-A81F-DE7A0EFA1083","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"bc938adb984a071edc79d3f9a5c31fc6e876eac6","datavalue":{"value":{"entity-type":"item","numeric-id":2075532,"id":"Q2075532"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"fcb6bf464a4b9ad09ba2cf122b3fe74637cf8026","datavalue":{"value":{"amount":"+0.7910383343696594","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":"Q278884$CF84AB4E-8BA4-40DF-8AF4-49EFED761F38","rank":"normal"},{"mainsnak":{"snaktype":"value","property":"P1643","hash":"1af0bdcc6649a7b9269564635d7ace141d2d4ead","datavalue":{"value":{"entity-type":"item","numeric-id":2447965,"id":"Q2447965"},"type":"wikibase-entityid"},"datatype":"wikibase-item"},"type":"statement","qualifiers":{"P1659":[{"snaktype":"value","property":"P1659","hash":"83fc2d4fa684f201730796887707e19994e6a6a1","datavalue":{"value":{"amount":"+0.7891245484352112","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":"Q278884$76E23FC2-EA53-45EA-AE30-C1DC769ADD5E","rank":"normal"}]},"sitelinks":{"mardi":{"site":"mardi","title":"Guessing games on triangle-free graphs","badges":[],"url":"https://portal.mardi4nfdi.de/wiki/Guessing_games_on_triangle-free_graphs"}}}}}