• Given a degree sequence, whether there exists a simple graph whose nodes satisfy the given degree sequence?
To solve the problem with 1 degree sequence, we have combinatorial recursive and matching approach as described here
• Given a degree sequence and a template, does there exist a sub-graph (having the given degree sequence) within the template? [P]
• Given 2 degree sequences, say red sequence and blue sequence, does there exist a simple graph (having edges of red and blue colors) and satisfying the given degree sequences?
• Given 2 degree sequences, say red sequence and blue sequence, and a template, does there exist a sub-graph (satisfying the given degree sequences) within the template? [NP-Hard]
• Given 3 (or more than 3 degree sequences) and a template, does there exist a sub-graph (satisfying the given degree sequences) within the template? [NP Hard]

Linear Programming Characterization

• [1] On Generating Graphs with Prescribed Degree Sequences for Complex Network Modeling Applications, Milena Mihail and Nisheeth Vishnoi.
• [2] Random Walks on Colored Graphs, Anne Condon and Diane Hernek.
• [3] Upper Degree-Constrained Partial Orientations, Harold N. Gabow.
• [4] A local switch Markov chain on given degree graphs with application in connectivity of Peer-to-Peer networks, Amin Saberi, Milena Mihail, Adam Guetz and Tomas Feder.
• [5] A Sequential Algorithm for Generating Random Graphs, Mohsen Bayati, Jeong Han Kim and Amin Saberi.
• [6] Efficient Generation of Graphical Partitions, Tiffany M. Barnes and Carla D. Savage.
• [7] A Recurrence for Counting Graphical Partitions, Tiffany M. Barnes and Carla D. Savage.
• [8] A Remark concerning Graphical Sequences, GeirDahl and Truls Flatberg.

• Graphic Sequence: http://mathworld.wolfram.com/GraphicSequence.html
• Graphical Partition: http://mathworld.wolfram.com/GraphicalPartition.html