{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,30]],"date-time":"2025-12-30T23:32:53Z","timestamp":1767137573851,"version":"build-2238731810"},"publisher-location":"Cham","reference-count":30,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030868376","type":"print"},{"value":"9783030868383","type":"electronic"}],"license":[{"start":{"date-parts":[[2021,1,1]],"date-time":"2021-01-01T00:00:00Z","timestamp":1609459200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2021,9,20]],"date-time":"2021-09-20T00:00:00Z","timestamp":1632096000000},"content-version":"vor","delay-in-days":262,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2021]]},"abstract":"<jats:title>Abstract<\/jats:title>\n                  <jats:p>\n                    Consider the following hat guessing game. A bear sits on each vertex of a graph\n                    <jats:italic>G<\/jats:italic>\n                    , and a demon puts on each bear a hat colored by one of\n                    <jats:italic>h<\/jats:italic>\n                    colors. Each bear sees only the hat colors of his neighbors. Based on this information only, each bear has to guess\n                    <jats:italic>g<\/jats:italic>\n                    colors and he guesses correctly if his hat color is included in his guesses. The bears win if at least one bear guesses correctly for any hat arrangement.\n                  <\/jats:p>\n                  <jats:p>\n                    We introduce a new parameter\u2014fractional hat chromatic number\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\hat{\\mu }$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    , arising from the hat guessing game. The parameter\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\hat{\\mu }$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    is related to the hat chromatic number which has been studied before. We present a surprising connection between the hat guessing game and the independence polynomial of graphs. This connection allows us to compute the fractional hat chromatic number of chordal graphs in polynomial time, to bound fractional hat chromatic number by a function of maximum degree of\n                    <jats:italic>G<\/jats:italic>\n                    , and to compute the exact value of\n                    <jats:inline-formula>\n                      <jats:tex-math>$$\\hat{\\mu }$$<\/jats:tex-math>\n                    <\/jats:inline-formula>\n                    of cliques, paths, and cycles.\n                  <\/jats:p>","DOI":"10.1007\/978-3-030-86838-3_22","type":"book-chapter","created":{"date-parts":[[2021,9,19]],"date-time":"2021-09-19T18:05:30Z","timestamp":1632074730000},"page":"283-295","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["Bears with Hats and Independence Polynomials"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0001-9165-6280","authenticated-orcid":false,"given":"V\u00e1clav","family":"Bla\u017eej","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6838-1538","authenticated-orcid":false,"given":"Pavel","family":"Dvo\u0159\u00e1k","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4389-5807","authenticated-orcid":false,"given":"Michal","family":"Opler","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2021,9,20]]},"reference":[{"key":"22_CR1","doi-asserted-by":"publisher","unstructured":"Aggarwal, G., Fiat, A., Goldberg, A.V., Hartline, J.D., Immorlica, N., Sudan, M.: Derandomization of auctions. In: Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, pp. 619\u2013625. STOC 2005. Association for Computing Machinery, New York, NY, USA, May 2005. https:\/\/doi.org\/10.1145\/1060590.1060682","DOI":"10.1145\/1060590.1060682"},{"key":"22_CR2","doi-asserted-by":"publisher","first-page":"119","DOI":"10.1016\/j.jctb.2020.01.003","volume":"144","author":"N Alon","year":"2020","unstructured":"Alon, N., Ben-Eliezer, O., Shangguan, C., Tamo, I.: The hat guessing number of graphs. J. Comb. Theory Ser. B 144, 119\u2013149 (2020). https:\/\/doi.org\/10.1016\/j.jctb.2020.01.003","journal-title":"J. Comb. Theory Ser. B"},{"key":"22_CR3","doi-asserted-by":"publisher","unstructured":"Blair, J.R.S., Peyton, B.: An introduction to chordal graphs and clique trees. In: George, A., Gilbert, J.R., Liu, J.W.H. (eds.) Graph Theory and Sparse Matrix Computation, pp. 1\u201329. Springer, New York (1993). https:\/\/doi.org\/10.1007\/978-1-4613-8369-7_1","DOI":"10.1007\/978-1-4613-8369-7_1"},{"key":"22_CR4","doi-asserted-by":"crossref","unstructured":"Bla\u017eej, V., Dvo\u0159\u00e1k, P., Opler, M.: Bears with hats and independence polynomials (2021). https:\/\/arxiv.org\/abs\/2103.07401","DOI":"10.1007\/978-3-030-86838-3_22"},{"key":"22_CR5","unstructured":"Bosek, B., Dudek, A., Farnik, M., Grytczuk, J., Mazur, P.: Hat chromatic number of graphs, May 2019. https:\/\/arxiv.org\/abs\/1905.04108"},{"issue":"2","key":"22_CR6","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1137\/060652774","volume":"22","author":"S Butler","year":"2008","unstructured":"Butler, S., Hajiaghayi, M.T., Kleinberg, R.D., Leighton, T.: Hat guessing games. SIAM J. Discrete Math. 22(2), 592\u2013605 (2008). https:\/\/doi.org\/10.1137\/060652774","journal-title":"SIAM J. Discrete Math."},{"key":"22_CR7","doi-asserted-by":"publisher","unstructured":"Diestel, R.: Graph Theory. Graduate Texts in Mathematics, Springer, Heidelberg (2017). https:\/\/doi.org\/10.1007\/978-3-662-53622-3","DOI":"10.1007\/978-3-662-53622-3"},{"key":"22_CR8","unstructured":"Ebert, T.: Applications of Recursive Operators to Randomness and Complexity. Ph.D. thesis, University of California, Santa Barbara (1998)"},{"issue":"6","key":"22_CR9","doi-asserted-by":"publisher","first-page":"1542","DOI":"10.1137\/S0097539702415317","volume":"32","author":"T Ebert","year":"2003","unstructured":"Ebert, T., Merkle, W., Vollmer, H.: On the autoreducibility of random sequences. SIAM J. Comput. 32(6), 1542\u20131569 (2003). https:\/\/doi.org\/10.1137\/S0097539702415317","journal-title":"SIAM J. Comput."},{"key":"22_CR10","unstructured":"Farnik, M.: A hat guessing game. Ph.D. thesis, Jagiellonian University (2015)"},{"key":"22_CR11","unstructured":"Feige, U.: You can leave your hat on (if you guess its color). Technical Report MCS04-03, The Weizmann Institute, Rehovot, Israel (2004)"},{"issue":"3","key":"22_CR12","doi-asserted-by":"publisher","first-page":"1922","DOI":"10.1137\/15M1044758","volume":"32","author":"M Gadouleau","year":"2018","unstructured":"Gadouleau, M.: Finite dynamical systems, hat games, and coding theory. SIAM J. Discrete Math. 32(3), 1922\u20131945 (2018). https:\/\/doi.org\/10.1137\/15M1044758","journal-title":"SIAM J. Discrete Math."},{"issue":"2","key":"22_CR13","doi-asserted-by":"publisher","first-page":"823","DOI":"10.1137\/130944680","volume":"29","author":"M Gadouleau","year":"2015","unstructured":"Gadouleau, M., Georgiou, N.: New constructions and bounds for Winkler\u2019s hat game. SIAM J. Discrete Math. 29(2), 823\u2013834 (2015). https:\/\/doi.org\/10.1137\/130944680","journal-title":"SIAM J. Discrete Math."},{"issue":"10","key":"22_CR14","doi-asserted-by":"publisher","first-page":"6703","DOI":"10.1109\/TIT.2011.2155618","volume":"57","author":"M Gadouleau","year":"2011","unstructured":"Gadouleau, M., Riis, S.: Graph-theoretical constructions for graph entropy and network coding based communications. IEEE Trans. Inf. Theory 57(10), 6703\u20136717 (2011). https:\/\/doi.org\/10.1109\/TIT.2011.2155618","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"1","key":"22_CR15","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1016\/0095-8956(74)90094-X","volume":"16","author":"F Gavril","year":"1974","unstructured":"Gavril, F.: The intersection graphs of subtrees in trees are exactly the chordal graphs. J. Comb. Theory Ser. B 16(1), 47\u201356 (1974). https:\/\/doi.org\/10.1016\/0095-8956(74)90094-X","journal-title":"J. Comb. Theory Ser. B"},{"key":"22_CR16","doi-asserted-by":"publisher","unstructured":"He, X., Li, R.: Hat guessing numbers of degenerate graphs. Electron. J. Comb. 27(3), P3.58 (2020). https:\/\/doi.org\/10.37236\/9449","DOI":"10.37236\/9449"},{"issue":"1","key":"22_CR17","doi-asserted-by":"publisher","first-page":"219","DOI":"10.1016\/0012-365X(94)90163-5","volume":"125","author":"C Hoede","year":"1994","unstructured":"Hoede, C., Li, X.: Clique polynomials and independent set polynomials of graphs. Discrete Math. 125(1), 219\u2013228 (1994). https:\/\/doi.org\/10.1016\/0012-365X(94)90163-5","journal-title":"Discrete Math."},{"issue":"4","key":"22_CR18","doi-asserted-by":"publisher","first-page":"718","DOI":"10.1137\/0210055","volume":"10","author":"I Holyer","year":"1981","unstructured":"Holyer, I.: The NP-completeness of edge-coloring. SIAM J. Comput. 10(4), 718\u2013720 (1981). https:\/\/doi.org\/10.1137\/0210055","journal-title":"SIAM J. Comput."},{"key":"22_CR19","unstructured":"Jin, K., Jin, C., Gu, Z.: Cooperation via codes in restricted hat guessing games. In: Proceedings of the 18th International Conference on Autonomous Agents and MultiAgent Systems, pp. 547\u2013555. AAMAS 2019. International Foundation for Autonomous Agents and Multiagent Systems, Richland, SC (2019)"},{"key":"22_CR20","unstructured":"Kokhas, K., Latyshev, A., Retinsky, V.: Cliques and constructors in \u201cHats\u201d game (2020). https:\/\/arxiv.org\/abs\/2004.09605"},{"key":"22_CR21","doi-asserted-by":"publisher","unstructured":"Kokhas, K., Latyshev, A.: Cliques and Constructors in \u201cHats\" Game. I. J. Math. Sci. 255(1), 39\u201357 (2021). https:\/\/doi.org\/10.1007\/s10958-021-05348-9","DOI":"10.1007\/s10958-021-05348-9"},{"key":"22_CR22","doi-asserted-by":"publisher","unstructured":"Kokhas, K.P., Latyshev, A.S., Retinskiy, V.I.: Cliques and Constructors in \u201cHats\" Game. II. J. Math. Sci. 255(1), 58\u201370 (2021). https:\/\/doi.org\/10.1007\/s10958-021-05349-8","DOI":"10.1007\/s10958-021-05349-8"},{"key":"22_CR23","doi-asserted-by":"crossref","unstructured":"Krzywkowski, M.P.: Hat problem on a graph. Ph.D. thesis, University of Exeter (2012)","DOI":"10.7494\/OpMath.2012.32.2.285"},{"issue":"4","key":"22_CR24","doi-asserted-by":"publisher","first-page":"546","DOI":"10.1002\/rsa.20439","volume":"41","author":"W Pegden","year":"2012","unstructured":"Pegden, W.: The lefthanded local lemma characterizes chordal dependency graphs. Random Struct. Algorithms 41(4), 546\u2013556 (2012)","journal-title":"Random Struct. Algorithms"},{"key":"22_CR25","doi-asserted-by":"publisher","unstructured":"Riis, S.: Information flows, graphs and their guessing numbers. Electron. J. Comb. 14(1), 962 (2007). https:\/\/doi.org\/10.37236\/962","DOI":"10.37236\/962"},{"key":"22_CR26","unstructured":"Robinson, S.: Why mathematicians now care about their hat color. New York Times, 10 April 2001. https:\/\/www.nytimes.com\/2001\/04\/10\/science\/why-mathematicians-now-care-about-their-hat-color.html"},{"key":"22_CR27","doi-asserted-by":"publisher","unstructured":"Scott, A.D., Sokal, A.D.: On dependency graphs and the lattice gas. Comb. Probab. Comput. 15(1\u20132), 253\u2013279 (2006). https:\/\/doi.org\/10.1017\/S0963548305007182","DOI":"10.1017\/S0963548305007182"},{"key":"22_CR28","doi-asserted-by":"publisher","unstructured":"Szczechla, W.: The three colour hat guessing game on cycle graphs. Electron. J. Comb. 24, 135 (2017). https:\/\/doi.org\/10.37236\/5135","DOI":"10.37236\/5135"},{"key":"22_CR29","doi-asserted-by":"publisher","unstructured":"Winkler, P.: Games people don\u2019t play. In: Wolfe, D., Rodgers, T. (eds.) Puzzlers\u2019 Tribute: A Feast for the Mind, pp. 301\u2013313 (2002). https:\/\/doi.org\/10.1201\/9781439864104-50","DOI":"10.1201\/9781439864104-50"},{"issue":"2","key":"22_CR30","doi-asserted-by":"publisher","first-page":"220","DOI":"10.1016\/j.jda.2008.09.009","volume":"7","author":"T Wu","year":"2009","unstructured":"Wu, T., Cameron, P., Riis, S.: On the guessing number of shift graphs. J. Discrete Algorithms 7(2), 220\u2013226 (2009). https:\/\/doi.org\/10.1016\/j.jda.2008.09.009","journal-title":"J. Discrete Algorithms"}],"updated-by":[{"DOI":"10.1007\/978-3-030-86838-3_31","type":"correction","label":"Correction","source":"publisher","updated":{"date-parts":[[2022,4,12]],"date-time":"2022-04-12T00:00:00Z","timestamp":1649721600000}}],"container-title":["Lecture Notes in Computer Science","Graph-Theoretic Concepts in Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-86838-3_22","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2023,12,8]],"date-time":"2023-12-08T15:04:41Z","timestamp":1702047881000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-86838-3_22"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021]]},"ISBN":["9783030868376","9783030868383"],"references-count":30,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-86838-3_22","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021]]},"assertion":[{"value":"20 September 2021","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"12 April 2022","order":2,"name":"change_date","label":"Change Date","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Correction","order":3,"name":"change_type","label":"Change Type","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Chapter [\u201cBears with Hats and Independence Polynomials\u201d] was previously published non-open access. It has now been changed to open access under a CC BY 4.0 license and the copyright holder updated to \u2018The Author(s)\u2019. The book has also been updated with this change.","order":4,"name":"change_details","label":"Change Details","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"WG","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Graph-Theoretic Concepts in Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Warsaw","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2021","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"23 June 2021","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"25 June 2021","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"47","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"wg2021","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Single-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"EasyChair and OCS","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"73","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"30","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"41% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"11","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"The conference was held online due to the COVID-19 pandemic.","order":10,"name":"additional_info_on_review_process","label":"Additional Info on Review Process","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}