Degree Game for Special Regular Graphs
For a given $d$-regular graph $G$, a Maker-Breaker degree game is played by two players who alternately claim previously unclaimed edges of $G$. In the standard variant, the goal of Maker is to maximize the maximum degree of their induced subgraph, while Breaker aims to minimize it, or equivalently, to guarantee a certain minimum degree in their own subgraph. A classic pairing strategy shows that Breaker can secure at least $\lfloor d/4 \rfloor$ edges at every vertex of any $d$-regular graph. Breaking this bound for general or even for specific classes of graphs has been a long-standing open…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2608.11007
curl -X POST /api/v1/records/arxiv/2608.11007/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2608.11007/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'