On edge-colouring-games by Erdős, and Bensmail and Mc Inerney
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914120374157312 |
|---|---|
| author | Cambie, Stijn Provoost, Michiel |
| author_facet | Cambie, Stijn Provoost, Michiel |
| contents | We study two games proposed by Erdős, and one game by Bensmail and Mc Inerney, all sharing a common setup: two players alternately colour edges of a complete graph, or in the biased version, they colour $p$ and $q$ edges respectively on their turns, aiming to maximise a graph parameter determined by their respective induced subgraphs. In the unbiased case, we give a first reduction towards confirming the conjecture of Bensmail and Mc Inerney, propose a conjecture for Erdős' game on maximum degree, and extend the clique and maximum-degree versions to edge-transitive and regular graphs. In the biased case, the maximum-degree and vertex-capturing games are resolved, and we prove the clique game with $(p,q)=(1,3)$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_03497 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On edge-colouring-games by Erdős, and Bensmail and Mc Inerney Cambie, Stijn Provoost, Michiel Combinatorics Discrete Mathematics Computer Science and Game Theory 05C15, 05C57, 91A10, 91A05, 91A43, 91A46, 91A68 We study two games proposed by Erdős, and one game by Bensmail and Mc Inerney, all sharing a common setup: two players alternately colour edges of a complete graph, or in the biased version, they colour $p$ and $q$ edges respectively on their turns, aiming to maximise a graph parameter determined by their respective induced subgraphs. In the unbiased case, we give a first reduction towards confirming the conjecture of Bensmail and Mc Inerney, propose a conjecture for Erdős' game on maximum degree, and extend the clique and maximum-degree versions to edge-transitive and regular graphs. In the biased case, the maximum-degree and vertex-capturing games are resolved, and we prove the clique game with $(p,q)=(1,3)$. |
| title | On edge-colouring-games by Erdős, and Bensmail and Mc Inerney |
| topic | Combinatorics Discrete Mathematics Computer Science and Game Theory 05C15, 05C57, 91A10, 91A05, 91A43, 91A46, 91A68 |
| url | https://arxiv.org/abs/2505.03497 |