Every tournament of dichromatic number $10 k^2$ has a vertex whose out-neighborhood has dichromatic number more than $k$
The dichromatic number of a tournament is the minimum number of colors needed to color the vertices so that no directed cycle is monochromatic. Nguyen, Scott, and Seymour (2025) asked whether every tournament with dichromatic number $2k$ has a vertex whose out-neighborhood induces a subtournament of dichromatic number at least $k$. We answer their question negatively by finding an example with dichromatic number $Ω(k^2)$. Furthermore, this quadratic bound is tight up to a constant factor; we show that for every integer $k \geq 1$, every tournament of dichromatic number $Ω(k^2)$ contains a…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.29043
curl -X POST /api/v1/records/arxiv/2610.29043/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.29043/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'