Graphs with Permutation-Representation Number at most Three

07/01/2023

∙

by   Khyodeno Mozhui, et al.

∙

0

∙

share

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.