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.
- Dantas, S.; Klein, S.; Mello, C.P.; Morgana, A. (2009), "The graph sandwich problem for P4-sparse graphs", Discrete Math, 309: 3664–3673.
- Golumbic, Martin Charles (1980), Algorithmic Graph Theory and Perfect Graphs, Academic Press, ISBN 0-444-51530-5 Second edition, Annals of Discrete Mathematics 57, Elsevier, 2004.
- Golumbic, Martin Charles; Kaplan, Haim; Shamir, Ron (1995), "Graph sandwich problems", J. Algorithms, 19: 449–473.
- Golumbic, Martin Charles; Trenk, Ann N. (2004), Tolerance Graphs, Cambridge.
- Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, North-Holland.