Faits: A. Les chemins de la Pleyeuse et de Pré Christian, à Verbier, appartiennent à des particuliers. Ils ont été construits progressivement à partir des années 1980 par A.X._ et B.X._, partiellement sur des fonds dont ils étaient à l'origine propriétaires, mais principalement sur ceux d'autrui. Par avis du 7 mars 2008, la commune de Bagnes a mis à l'enquête un plan d'expropriation des chemins de la Pleyeuse et de Pré Christian. La réalisation de ce plan impliquait l'expropriation complète de la parcelle n° 3084, dont A.X._ et B.X._ sont copropriétaires pour moitié chacun. Grevée depuis 1979 de nombreuses servitudes de passage pour véhicules et de conduites en tout genre, ce bien-fonds d'environ 100 m de long pour une surface de 648 m2 correspond au départ du chemin de la Pleyeuse dès la route communale du Golf. Le 10 septembre 2008, le Conseil d'Etat du canton du Valais a approuvé le projet communal et déclaré les travaux y relatifs d'utilité publique. La Cour de droit public du Tribunal cantonal du canton du Valais a partiellement confirmé cette décision le 5 mars 2009, sous réserve de l'examen des prétentions des frères X._ en paiement d'une indemnité d'expropriation dans la procédure d'estimation prévue par la loi cantonale sur les expropriations que la Commune de Bagnes était invitée à initier. Dans ce cadre, A.X._ et B.X._ ont réclamé une indemnité de 1'131'000 fr. ou d'un montant à déterminer par expertise, avec intérêts à 5 % dès le 15 octobre 2008. Par prononcé du 17 novembre 2010, la Commission d'estimation en matière d'expropriation a rejeté cette requête, considérant qu'aucune indemnité n'était due pour le transfert de routes privées dans le domaine public communal lorsque l'usage commun restait ouvert à l'exproprié. Statuant par arrêt du 17 mars 2011, le Tribunal cantonal a admis partiellement le recours formé par A.X._ et B.X._ contre ce prononcé et renvoyé la cause à la Commission d'estimation pour nouvelle décision. Il a confirmé que, la parcelle n° 3084 étant inconstructible et n'ayant aucune valeur vénale, les recourants n'avaient en principe aucun droit à une indemnité pour la surface expropriée. Il a admis en revanche que devait être examiné le droit des expropriés à être indemnisés pour la perte de leurs créances potentielles envers les propriétaires de quatre parcelles non encore raccordées aux chemins de la Pleyeuse et de Pré Christian. Par décision du 22 mars 2012, la Commission d'estimation a constaté que les frères X._ n'avaient pas à être indemnisés pour le transfert de leur parcelle dans le domaine public. B. Saisi d'un recours des expropriés, le Tribunal cantonal a confirmé cette décision par arrêt du 10 octobre 2012. A l'instar de la Commission d'estimation, il a considéré que les frères X._ n'avaient aucune expectative en remboursement de la part des propriétaires desservis par les chemins litigieux. Il a rappelé pour le surplus que la parcelle, non constructible - ce également s'agissant des portions non comprises dans l'assiette des servitudes de passage -, n'avait aucune valeur vénale, de sorte qu'aucun dommage ne pouvait être retenu. C. Agissant par la voie du recours en matière de droit public, A.X._ et B.X._ demandent au Tribunal fédéral de réformer cet arrêt en ce sens que la commune de Bagnes est condamnée au paiement de 1'131'000 fr. avec intérêts à 5 % dès le 15 octobre 2008. Le Tribunal cantonal et la Commission d'estimation renoncent à se déterminer. La commune se réfère aux considérants de l'arrêt attaqué et conclut au rejet du recours. 