Interval Graphs are Reconstructible
| Title: | Interval Graphs are Reconstructible |
|---|---|
| Authors: | Heinrich, Irene, Kiyomi, Masashi, Otachi, Yota, Schweitzer, Pascal |
| Publication Year: | 2025 |
| Collection: | Computer Science Mathematics |
| Subject Terms: | Mathematics - Combinatorics, Computer Science - Discrete Mathematics, Computer Science - Data Structures and Algorithms, 68R10, 68Q25, F.2.2, G.2.2 |
| More Details: | 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. Comment: 40 pages, 1 figure |
| Document Type: | Working Paper |
| Access URL: | http://arxiv.org/abs/2504.02353 |
| Accession Number: | edsarx.2504.02353 |
| Database: | arXiv |
| Description not available. |