2025/04/03 by Irene Heinrich, Heinrich, Irene, Masashi Kiyomi +5
Engineering · Computer Science · #VLSI and FPGA Design Techniques #Formal Methods in Verification #Advanced Graph Theory Research
paper · pdf · doi:10.48550/arxiv.2504.02353
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.