I have 2 questions.
Firstly, I am not sure about differences between Permutaion Graphs and Comparability Graphs. The latter graph class includes the other class. Is there a specific example of graph which is is in Comparability Class but is not in Permutation Class ?
Secondly, There are several fast algorithm for vertex coloring of permutaion graph like poly time algorithms using dynamic way or NC parralel algorithms. Can we solve vertex colroing via converting instances of coloring to instances of 2-SAT? I think this solution is plausible, because any permutaion can be represented by several transpositions and we may be able to construct clause whose length is 2 using such transpositions.