Graph sandwich problem

In graph theory and computer science, the graph sandwich problem is a problem of finding a graph that belongs to a particular family of graphs and is "sandwiched" between two other graphs, one of which must be a subgraph and the other of which must be a supergraph of the desired graph.

Graph sandwich problems generalize the problem of testing whether a given graph belongs to a family of graphs, and have attracted attention because of their applications and as a natural generalization of recognition problems.[1]

## Problem statement

More precisely, given a vertex set V, a mandatory edge set E1, and a (potentially) larger edge set E2, a graph G = (V, E) is called a sandwich graph for the pair G1 = (V, E1), G2 = (V, E2) if E1 ⊆ E ⊆ E2. The graph sandwich problem for property Π is defined as follows:Cite error: Closing `</ref>` missing for `<ref>` tag It can be solved in polynomial time for split graphs,[2][3] threshold graphs,[2][3] and graphs in which every five vertices contain at most one four-vertex induced path.[4] The complexity status has also been settled for the H-free graph sandwich problems for each of the four-vertex graphs H.[5]

## References

1. ↑ Golumbic, Martin Charles; Trenk, Ann N. (2004), "Chapter 4. Interval probe graphs and sandwich problems", Tolerance Graphs, Cambridge, pp. 63–83 .
2. ↑ 2.0 2.1 Cite error: Invalid `<ref>` tag; no text was provided for refs named `gks`
3. ↑ 3.0 3.1 Mahadev, N.V.R.; Peled, Uri N. (1995), Threshold Graphs and Related Topics, Annals of Discrete Mathematics, 57, North-Holland, pp. 19–22, ISBN 978-0-08-054300-0, https://books.google.com/books?id=nWfGo_VX5M8C&pg=PA19 .
4. ↑ Dantas, S.; Klein, S.; Mello, C.P.; Morgana, A. (2009), "The graph sandwich problem for P4-sparse graphs", Discrete Mathematics 309 (11): 3664–3673, doi:10.1016/j.disc.2008.01.014 .
5. ↑ Dantas, Simone; de Figueiredo, Celina M.H.; Maffray, Frédéric; Teixeira, Rafael B. (2013), "The complexity of forbidden subgraph sandwich problems and the skew partition sandwich problem", Discrete Applied Mathematics 182: 15–24, doi:10.1016/j.dam.2013.09.004 .

## Further reading

* Dantas, Simone; de Figueiredo, Celina M.H.; da Silva, Murilo V.G.; Teixeira, Rafael B. (2011), "On the forbidden induced subgraph sandwich problem", Discrete Applied Mathematics 159 (16): 1717–1725, doi:10.1016/j.dam.2010.11.010 .

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Graph sandwich problem. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Graph_sandwich_problem&oldid=4157833"