Bounded-Defect Proper Orientations and Graphs on Surfaces
Abstract
Chen, Mohar and Wu [J. Combin. Theory Ser. B 161 (2023)] conjectured that every graph of orientable genus g has proper orientation number O(√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∈ℤ≥0. If G has maximum average degree at most 2k and V(G)=V1∪ V2∪ V3, where each Vi induces a subgraph of maximum degree at most D, then pchi(G)≤ k+9D+6+floor3/2ceil(2D+2)/5≤ k+floor48D/5+8. When the partition is given, we construct such an orientation in polynomial time. For every D≥1, we also construct a graph with a partition into three parts of internal maximum degree at most D for which pchi(G)−ceilmad(G)/2≥6D+5; hence the linear dependence on D is unavoidable. Finally, Woodall's defective-coloring theorem yields pchi(G)=O(√(γ+1)) for every graph of Euler genus γ.
Related
- Proper Conflict-Free Choosability for Graphs with Bounded Average Degree
- Incidence Rank and Bounded Defect for Linear Hypergraphs with Cograph Line Graphs
- Modulo k-orientations of highly edge-connected signed graphs
- Chains and unique transitive orientations of prime graphs
- The proper geometric dimension of the mapping class groups of non-orientable surfaces with punctures
BibTeX
@misc{wu2026boundeddefect,
title = {{Bounded-Defect Proper Orientations and Graphs on Surfaces}},
author = {Qi Wu and Yong Lu},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.30315},
eprint = {2609.30315},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.30315},
note = {CC0},
}
RIS
TY - UNPB
TI - Bounded-Defect Proper Orientations and Graphs on Surfaces
AU - Qi Wu
AU - Yong Lu
PY - 2026
DA - 2026/09/01
PB - arXiv
DO - 10.48550/arxiv.2609.30315
UR - https://arxiv.org/abs/2609.30315
AB - Chen, Mohar and Wu [J. Combin. Theory Ser. B 161 (2023)] conjectured that every graph of orientable genus g has proper orientation number O(√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∈ℤ_≥0. If G has maximum average degree at most 2k and V(G)=V_1∪ V_2∪ V_3, where each V_i induces a subgraph of maximum degree at most D, then pchi(G)≤ k+9D+6+floor3/2ceil(2D+2)/5≤ k+floor48D/5+8. When the partition is given, we construct such an orientation in polynomial time. For every D≥1, we also construct a graph with a partition into three parts of internal maximum degree at most D for which pchi(G)−ceilmad(G)/2≥6D+5; hence the linear dependence on D is unavoidable. Finally, Woodall's defective-coloring theorem yields pchi(G)=O(√(γ+1)) for every graph of Euler genus γ.
ER -