New results on proper orientation number of graphs
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914617340461056 |
|---|---|
| author | Wang, Laochao Wang Xiaolin Yu, Guangmiao |
| author_facet | Wang, Laochao Wang Xiaolin Yu, Guangmiao |
| contents | 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 \frac{1}{2} \text{Mad}(G)\rceil$ can be bounded by a linear function of $r$.
In this paper, we first construct somewhat involved $r$-partite graphs with $\vecχ(G)\geq\lceil \frac{1}{2} \text{Mad}(G)\rceil +\lfloor\frac{5}{2}r\rfloor-2$, showing that a linear dependence on \(r\) is unavoidable. We also prove that $ \vecχ(G) \leq\lceil \frac{1}{2} \text{Mad}(G)\rceil +7$ for every 3-partite graph $G$. This implies \(\vecχ(G)\le 10\) for \(3\)-colorable planar graphs and \(\vecχ(G)\le 9\) for outerplanar graphs, improving the corresponding bounds of Chen, Mohar, and Wu. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_14670 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | New results on proper orientation number of graphs Wang, Laochao Wang Xiaolin Yu, Guangmiao Combinatorics 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 \frac{1}{2} \text{Mad}(G)\rceil$ can be bounded by a linear function of $r$. In this paper, we first construct somewhat involved $r$-partite graphs with $\vecχ(G)\geq\lceil \frac{1}{2} \text{Mad}(G)\rceil +\lfloor\frac{5}{2}r\rfloor-2$, showing that a linear dependence on \(r\) is unavoidable. We also prove that $ \vecχ(G) \leq\lceil \frac{1}{2} \text{Mad}(G)\rceil +7$ for every 3-partite graph $G$. This implies \(\vecχ(G)\le 10\) for \(3\)-colorable planar graphs and \(\vecχ(G)\le 9\) for outerplanar graphs, improving the corresponding bounds of Chen, Mohar, and Wu. |
| title | New results on proper orientation number of graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2604.14670 |