A necessary and sufficient condition for the existence of \p,p+1,q-1,q\-orientations in simple graphs

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

paper · doi:10.48550/arxiv.2205.10883

Abstract

Let G be a simple graph and let p and q be two integer-valued functions on V(G) with p< q in which for each v∈ V(G), q(v) ≥ (1)/(2)d_G(v) and p(v) ≥ (1)/(2) q(v)-2. In this note, we show that G has an orientation such that for each vertex v, d⁺_G(v)∈\p(v),p(v)+1,q(v)-1,q(v)\ if and only if it has an orientation such that for each vertex v, p(v) ≤ d⁺_G(v)≤ q(v) where d⁺_G(v) denotes the out-degree of v in G. From this result, we refine a result due to Addario-Berry, Dalal, and Reed (2008) in bipartite simple graphs on the existence of degree constrained factors.

Related

• The existence of \p,q\-orientations in edge-connected graphs
• On orientations with forbidden out-degrees
• On the complexity of finding well-balanced orientations with upper bounds on the out-degrees
• Counting degree-constrained orientations
• A characterization on (g,f)-parity orientations