New results on proper orientation number of graphs
The proper orientation number $\vecχ(G)$ of an undirected graph $G$ is the minimum $k$ such that there exists an orientation of $G$ with all out-degrees at most $k$ and with different out-degrees for any two adjacent vertices. Chen, Mohar and Wu (JCTB, 2023) proved that if $G$ is a $r$-partite graph, then $\vecχ(G) \leq \frac{1}{2} \text{Mad}(G)+r^{1+o(1)}$, where $\text{Mad}(G)$ is the maximum average degree of $G$. Moreover, if $G$ is a bipartite graph, then $ \vecχ(G) \leq \lceil \frac{1}{2} \text{Mad}(G)\rceil +3$ and this bound is tight. They also asked whether $\vecχ(G)-\lceil…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2604.14670
curl -X POST /api/v1/records/arxiv/2604.14670/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2604.14670/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'