2022/02/28 by Hörsch, Florian, Szigeti, Zoltán
#Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.2202.13759
We show that the problem of deciding whether a given graph G has a well-balanced orientation G such that d_G+(v)≤ ℓ(v) for all v ∈ V(G) for a given function ℓ:V(G)→ ℤ≥ 0 is NP-complete. We also prove a similar result for best-balanced orientations. This improves a result of Bern' ath, Iwata, Kir' aly, Király and Szigeti and answers a question of Frank.