MAD Phase Transitions in the Oriented Chromatic Number
For an oriented graph $G$ the oriented chromatic number of $G$, written $χ_o(G)$, is the least integer $t$ such that $G$ has a homomorphism to a tournament on $t$ vertices. The oriented chromatic number of a simple graph $H$ is the maximum oriented chromatic number over all orientations of $H$. Borodin, Kostochka, Ne{š}et{ř}il, Raspaud, and Sopena proved in 1999 that for all $ε>0$, graphs with maximum average degree less than $4-ε$ have bounded oriented chromatic number. This is in some sense optimal, because $1$-subdivisions of cliques demonstrate that there exists graphs with maximum…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2607.22915
curl -X POST /api/v1/records/arxiv/2607.22915/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2607.22915/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'