Salvato in:
| Autori principali: | , , , , , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2026
|
| Soggetti: | |
| Accesso online: | https://arxiv.org/abs/2603.04909 |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866917315942023168 |
|---|---|
| author | Adriaensen, Sam Bentley, Peter Bishnoi, Anurag Kreiger, Michael van der Kuil, Lars Mandal, Saptarshi Ramachandran, Anurag Tuite, James |
| author_facet | Adriaensen, Sam Bentley, Peter Bishnoi, Anurag Kreiger, Michael van der Kuil, Lars Mandal, Saptarshi Ramachandran, Anurag Tuite, James |
| contents | We initiate the study of the hat guessing number of a graph where the adversary is only allowed to provide a proper coloring of the graph. This is the largest number $q$ for which there is a guessing strategy on each vertex that only depends on its neighborhood, such that for every proper coloring of the graph with $q$ colors at least one vertex guesses its color correctly. In this variation, we prove that the hat guessing number of the complete graphs on $n$ vertices is $2n - 1$, which is roughly twice the classical hat guessing number of the complete graph. Our winning strategy is related to finding perfect matchings between the middle layers of the boolean poset of dimension $2n - 1$. We prove that the hat guessing number of all trees on $n \geq 3$ vertices is equal to $4$. We derive some general upper and lower bounds for all graphs and give improved estimates for book graphs. Using our results and an ILP formulation of the problem, we determine the exact hat guessing number for all graphs on at most $4$ vertices, give bounds on graphs on $5$ vertices, and propose general conjectures. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2603_04909 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Hat guessing with proper colorings Adriaensen, Sam Bentley, Peter Bishnoi, Anurag Kreiger, Michael van der Kuil, Lars Mandal, Saptarshi Ramachandran, Anurag Tuite, James Combinatorics We initiate the study of the hat guessing number of a graph where the adversary is only allowed to provide a proper coloring of the graph. This is the largest number $q$ for which there is a guessing strategy on each vertex that only depends on its neighborhood, such that for every proper coloring of the graph with $q$ colors at least one vertex guesses its color correctly. In this variation, we prove that the hat guessing number of the complete graphs on $n$ vertices is $2n - 1$, which is roughly twice the classical hat guessing number of the complete graph. Our winning strategy is related to finding perfect matchings between the middle layers of the boolean poset of dimension $2n - 1$. We prove that the hat guessing number of all trees on $n \geq 3$ vertices is equal to $4$. We derive some general upper and lower bounds for all graphs and give improved estimates for book graphs. Using our results and an ILP formulation of the problem, we determine the exact hat guessing number for all graphs on at most $4$ vertices, give bounds on graphs on $5$ vertices, and propose general conjectures. |
| title | Hat guessing with proper colorings |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2603.04909 |