Graph sandwich problem
In graph theory and computer science, the graph sandwich problem is the study of incomplete models of pairwise relations between objects from a certain collection, and how to complete them.
Given a vertex set V, a mandatory edge set E1, and a larger edge set E2, a graph G = (V, E) is called a sandwich graph for the pair G1, G2 if E1 ⊆ E ⊆ E2. The graph sandwich problem for property Π is defined as follows:
Graph Sandwich Problem for Property Π:
Instance: Vertex set V and edge sets
E1 ⊆ E2 ⊆ V × V.
Question: Is there a graph G = (V, E) such that E1 ⊆ E ⊆ E2 and G satisfies property Π ?
References
- Bondy, J.A.; Murty, U.S.R. (2008), Graph Theory, Springer, ISBN 978-1-84628-969-9.
- Golumbic, Martin (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press.
- Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, North-Holland.