Interval Graphs are Reconstructible
This resolves a major open problem in graph reconstruction theory for the class of interval graphs, providing a new technique that may apply to other graph classes.
The authors prove that interval graphs with at least three vertices are reconstructible, resolving a long-standing open problem. They also show that interval graphs can be reconstructed in polynomial time.
A graph is reconstructible if it is determined up to isomorphism by the multiset of its proper induced subgraphs. The reconstruction conjecture postulates that every graph of order at least 3 is reconstructible. We show that interval graphs with at least three vertices are reconstructible. For this purpose, we develop a technique to handle separations in the context of reconstruction. This resolves a major roadblock to using graph structure theory in the context of reconstruction. To apply our novel technique, we also develop a resilient combinatorial structure theory for interval graphs. A consequence of our result is that interval graphs can be reconstructed in polynomial time.