Research reveals the relationship between orientation and list-orientation numbers in various graph classes, suggesting important implications for graph theory.
The orientation number of a graph G , denoted by o ( G ) , is the minimum integer k such that there exists an orientation D with d D + ( v ) ≤ k for every v ∈ V ( G ) , where d D + ( v ) is the out-degree of v in the directed graph G with respect to the orientation D . In this paper, we define its list-analog as the list-orientation number o ℓ ( G ) , and conjecture that o ℓ ( G ) ≤ o ( G ) + 2 for every graph G . We give partial solutions and tight constructions for this conjecture for some fundamental classes of graphs, such as bipartite graphs, graphs with o ( G ) ≤ 2 , and planar graphs. In addition, we extend some of the results from unsigned graphs to signed ones.
No takes yet. Share an insight, caveat, or question.
Abe et al. (2026) studied this question.
Synapse has enriched 2 closely related papers on similar clinical questions. Consider them for comparative context: