Efficient characterizations of \(n\)-chromatic absolute retracts (Q1186122)

An absolute retract is a graph (without loops) for which every isometric embedding into another graph with the same chromatic number is a coretraction. Absolute retracts of graphs can be regarded as the injective objects of a suitable category: the objects are coloured spaces with integer metrics (such as coloured graphs) and the morphisms are non- expansive mappings preserving colours. Hitherto only bipartite absolute retracts were known to admit efficient characterizations. The authors prove some characterizations by which \(n\)-chromatic absolute retracts can be recognized in polynomial time. These procedures either directly test the solvability of certain systems of distance inequalities under colour constraints or recursively operate on neighbourhood lists and dismantle the graph vertex by vertex.