Specialization of Erdos Gallai Theorem To Vertex Exclusions

74 Views Asked by At

The Erdos Gallai theorem says that a degree sequence $d=(d_1,\cdots,d_n)$ corresponds to a graph iff it satisfies:

$$\sum_{i=1}^kd_i\leq k(k-1)+\sum_{i=k+1}^n\min(k,d_i).$$

Is there a specialization of this result to allow for additional exclusions on possible connections in the graph? Something like for each vertex $v_i$ there is an exclusion list of vertices which cannot connect to $v_i$? For example, $v_1$ cannot connect to $v_2,v_3$.