Bounded-Defect Proper Orientations and Graphs on Surfaces
Chen, Mohar and Wu [J. Combin. Theory Ser. B 161 (2023)] conjectured that every graph of orientable genus $g$ has proper orientation number $O(\sqrt g)$. We prove this conjecture. Our main result extends the potential-outdegree method from independent color classes to three parts of bounded internal degree. Let $k,D\in\mathbb Z_{\ge0}$. If $G$ has maximum average degree at most $2k$ and $V(G)=V_1\cup V_2\cup V_3$, where each $V_i$ induces a subgraph of maximum degree at most $D$, then $$\pchi(G)\le k+9D+6+\floor{\frac32\ceil{\frac{2D+2}{5}}}\le k+\floor{\frac{48D}{5}}+8.$$ When the partition…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.30315
curl -X POST /api/v1/records/arxiv/2609.30315/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.30315/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'