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.
[ cf., https://arxiv.org/abs/2504.02353 ]
[Marthe Bonamy] (LaBRI)
https://www.labri.fr/perso/mbonamy/
Vérifiez que vous êtes bien inscrits sur le site du [gdr-ifm-gt-graphes] : [ https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres | https://gtgraphes.labri.fr/pmwiki/pmwiki.php/Equipes/Equipes#membres ]
Remarks / Remarques
Find all the information of the working group on this [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT?userlang=en | web page ] .
Retrouvez toutes les informations du GT sur cette [ https://graphesetoptimisation.labri.fr/pmwiki.php/Groupe/GT | page web ] .