Squares of Low Maximum Degree
  A graph H is a square root of a graph G if G can be obtained from H by adding an edge between any two vertices in H that are of distance 2. The Square Root problem is that of deciding whether a given graph admits a square root. This problem is only known to be NP-complete for chordal graphs and polynomial-time solvable for non-trivial minor-closed graph classes and a very limited number of other graph classes. We prove that Square Root is O(n)-time solvable for graphs of maximum degree 5 and O(n^4)-time solvable for graphs of maximum degree at most 6. 
Manfred Cochefert, Jean-Fran\c{c}ois Couturier, Petr A. Golovach,   Dieter Kratsch, Dani\"el Paulusma, and Anthony Stewart
cs.DS cs.DM math.CO