{"id":"arxiv/2604.14670","url":"https://arxiv.org/abs/2604.14670","tags":["math.CO"],"score":0,"title":"New results on proper orientation number of graphs","domain":"math.CO","source":"arxiv","authors":["Laochao Wang Xiaolin Wang","Guangmiao Yu"],"reviews":0,"subject":"math.CO","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-04-16","reactions":{}}