Modulo orientations with bounded out-degrees

2017/02/22 by Hasanvand, Morteza
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1702.07039

Abstract

Let G be a graph, let k be a positive integer, and let p:V(G)→ Z_k be a mapping with |E(G)| \stackrelk≡∑_{v∈ V(G)}p(v) . In this paper, we show that if G is (3k-3)-edge-connected, then it has an orientation such that for each vertex v, |d⁺_G(v)-d_G(v)/2| < k; also if G contains 2k-2 edge-disjoint spanning trees, then it admits such an orientation but by imposing greater out-degree bounds.

Related

• The existence of \p,q\-orientations in edge-connected graphs
• Counting degree-constrained orientations
• On the In-Out-Proper Orientations of Graphs
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• On the proper orientation number of chordal graphs