Graphs with Permutation-Representation Number at most Three

In this paper, firstly, we reconcile the graphs with permutation-representation number at most two. While the characterization of the class of graphs with permutation-representation number at most three is an open problem, we show that the trees and the even cycles belong to this class. In this connection, we give polynomial-time algorithms for obtaining words representing the trees and the even cycles permutationally.